「ZJOI2014」力

题目链接：Click here

Solution:

把式子拿下来

\[E_k=\sum_{i=1}^{k-1} {q_i \over (k-i)^2} -\sum_{i=k+1} ^ n {q_i \over (i-k)^2} \]

构造一个生成函数\(C(x)=\sum_{i=1}^n {1 \over i^2} x^i\)，那么式子就变成了这样

\[E_k=\sum_{i=1}^{k-1} q_i C_{k-i} -\sum_{i=k+1} ^ n q_i C_{i-k} \]

我们把\(q(x)\,\,reverse\)一下，得到新的多项式\(p(x)\)，那么式子就是这个样子的了

\[E_k=\sum_{i=1}^{k-1} q_i C_{k-i} -\sum_{i=k+1} ^ n p_{n-i+1} C_{i-k} \]

可以发现，两项都是卷积的形式，令\(A=q\times C\)，\(B=p\times C\)，则\(E_k=A_k-B_{n-k+1}\)

于是直接上\(FTT\)即可，时间复杂度\(O(n \log n)\)

Code：

#include
#define Pi acos(-1.0)
using namespace std;
const int N=4e5+11;
int n,m,k,len=1,tim,p[N];
struct Complex{double x,y;}a[N],b[N],c[N];
Complex operator + (Complex A,Complex B){return (Complex){A.x+B.x,A.y+B.y};}
Complex operator - (Complex A,Complex B){return (Complex){A.x-B.x,A.y-B.y};}
Complex operator * (Complex A,Complex B){return (Complex){A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x};}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void FFT(Complex *v,int flag){
    for(int i=0;i>1);u++,w=w*wn){
                Complex x=v[u],y=w*v[u+(l>>1)];
                v[u]=x+y;v[u+(l>>1)]=x-y;
            }    
        }
    }
}
signed main(){
    n=read();++n;
    for(int i=1;i>1]>>1)|((i&1)<<(tim-1));
    FFT(a,1);FFT(b,1);FFT(c,1);
    for(int i=0;i