传送门：https://www.luogu.com.cn/problem/P3338
题意
$$F_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i\times q_j}{(i-j)^2}$$
$$求解E_i=\frac{F_i}{q_i}$$
思路
$首先来看看什么是卷积：C_k=\sum_{i=0}^kA_iB_{k-i}，所以要想办法将上式转化成卷积的形式，然后FFT加速求解。$
$左右都加上一个i=j的情况（式子总体不变）。$ $$E_j=\frac{F_j}{q_j}=\sum_{i=1}^{j}\frac{q_i}{(i-j)^2}-\sum_{i=j}^{n}\frac{q_i}{(i-j)^2}$$
$设f[i]=q_i，g[i]=\frac{1}{i^2}得（并且f[0]=g[0]=0）：$
$$E_j=\sum_{i=0}^{j}f[i][j - i]-\sum_{i=j}^{n}f[i]g[i-j]$$
$这时候，左边 已经是卷积的形式了，所以就只要将右边转化一下即可。$
$先将右边展开得：$
$\sum_{i=j}^{n}f[i]g[i-j]=f[j]g[0]+f[j+1][1]+…+f[n]g[n-j]$ $\sum_{i=j}^{n}f[i]g[i-j]=\sum_{i=0}^{n-j}f[i+j]g[i]$
$怎么转化成卷积形式呢，只需要将f翻转一下变成f’即可，即f’[i]=f[n-i]，并令t=n-j，得下式：$
$$\sum_{i=0}^{n-j}f[i+j]g[i]=\sum_{i=0}^tf’[t-i]g[i]$$
$合并一下，得下式：$
$$E_j=\sum_{i=0}^{j}f[i][j - i]-\sum_{i=0}^tf’[t-i]g[i]$$
$令L(x)=\sum_{i=0}^nf(n)\times g(n)，R(x)=\sum_{i=0}^nf’(n)\times g(n)$
$则E_i=L(i)-R(n-i)$
$先预处理f,f’,g，最后用FFT加速卷积即可。$
Code（921ms）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const double PI = acos(-1);
const int N = 3e5 + 10;
struct Complex {
double r, i;
Complex() {r == 0; i = 0;};
Complex(double real, double imag) : r(real), i(imag) {};
}A[N], B[N], C[N];
Complex operator + (Complex a, Complex b) {
return Complex(a.r + b.r, a.i + b.i);
}
Complex operator - (Complex a, Complex b) {
return Complex(a.r - b.r, a.i - b.i);
}
Complex operator * (Complex a, Complex b) {
return Complex(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
}
int rev[N], len, lim = 1;
void FFT(Complex *a, int opt) {
for(int i = 0;i < lim; i++) {
if(i < rev[i])
swap(a[i], a[rev[i]]);
}
for(int dep = 1;dep <= log2(lim); dep++) {
int m = 1 << dep;
Complex wn = Complex(cos(2.0 * PI / m), opt * sin(2.0 * PI / m));
for(int k = 0;k < lim; k += m) {
Complex w = Complex(1, 0);
for(int j = 0;j < m / 2; j++) {
Complex t = w * a[k + j + m / 2];
Complex u = a[k + j];
a[k + j] = u + t;
a[k + j + m / 2] = u - t;
w = w * wn;
}
}
}
if(opt == -1) {
for(int i = 0;i < lim; i++) a[i].r /= lim;
}
}
void solve() {
int n;
scanf("%d",&n);
while(lim <= (n << 1)) {
lim <<= 1;
len++;
}
for(int i = 0;i < lim; i++) rev[i] = (rev[i >> 1] >> 1) ((i & 1) << (len - 1));
for(int i = 1;i <= n; i++) {
scanf("%lf",&A[i].r);
B[i].r = (double)(1.0 / i / i);
C[n - i].r = A[i].r;
}
FFT(A, 1);
FFT(B, 1);
FFT(C, 1);
for(int i = 0;i <= lim; i++) {
A[i] = A[i] * B[i];
C[i] = C[i] * B[i];
}
FFT(A, -1);
FFT(C, -1);
for(int i = 1;i <= n; i++) {
printf("%.3lf\n",A[i].r - C[n - i].r);
}
}
signed main() {
ios_base::sync_with_stdio(false);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/10/08/luogu-p3338/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！