P3338 [ZJOI2014]力

P3338 [ZJOI2014]力 卷积 + FFT

题意思路Code（921ms） 传送门： 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}^k{A}_i{B}_{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^{\prime }即可，即f^{\prime }[i]=f[n-i]，并令t=n-j，得下式：$

$$\sum _{i=0}^{n-j}f[i+j]g[i]=\sum _{i=0}^t{f}^{\prime }[t-i]g[i]$$

$合并一下，得下式：$

$$E_j=\sum _{i=0}^{j}f[i][j-i]-\sum _{i=0}^t{f}^{\prime }[t-i]g[i]$$

$令L(x)={\sum }_{i=0}^{n}f(n)\times g(n)，R(x)={\sum }_{i=0}^n{f}^{\prime }(n)\times g(n)$

$则E_i=L(i)-R(n-i)$

$先预处理f,f^{\prime },g，最后用FFT加速卷积即可。$

Code（921ms）

#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 ll mod = 998244353; // const ll mod = 1e9 + 7; // const double eps = 1e-6; 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); //cin.tie(nullptr); //cout.tie(nullptr); #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; }