P3338 [ZJOI2014]力 题解
题面
看这个题目的式子，好像就是最近学的库仑定律+电场强度？？做法推式子FFT。
考虑首先通过 \(E_i=\frac{F_i}{q_i}\) 消掉原式中的一些量。得到：
\[E_i=\sum_{i=0}^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}\)，可得
\[\begin{aligned} E_i&=\sum_{i=0}^{j}g[j-i]f[i]-\sum_{i=j}^{n}g[j-i]f[i]\\ &=\sum_{i=0}^{j}g[j-i]f[i]-\sum_{i=0}^{n-j}f[j+i]g[i] \end{aligned} \]典型的 \(\min\) 卷积形式，一般做法是考虑翻转。令 \(f'[i]=f[n-i]\)，可得
\[\begin{aligned} E_i&=\sum_{i=0}^{j}g[j-i]f[i]-\sum_{i=0}^{n-j}f'[n-j-i]g[i]\\ &=\sum_{i=0}^{j}g[j-i]f[i]-\sum_{i=0}^{t}f'[t-i]g[i] \end{aligned} \]这样就化成两个卷积的形式了，最后就把两个多项式卷一下然后用每一项系数求答案即可。\(ans_i=l_i-r_{n-i}\)。
点击查看代码
#include
#include
#include
using namespace std;
const int N=4e5+13;
const double Pi=acos(-1);
struct complex{
double x,y;
complex(double xx=0,double yy=0){x=xx,y=yy;}
complex operator +(const complex &a)const{return complex(x+a.x,y+a.y);}
complex operator -(const complex &a)const{return complex(x-a.x,y-a.y);}
complex operator *(const complex &a)const{return complex(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N],b[N];
int n,r[N];
double A[N],B[N],C[N],L[N],R[N];
inline void fft(complex *f,int limit,int type){
for(int i=0;i>1]>>1)|((i&1)<<(l-1));
for(int i=0;i