[ZJOI2014] 力 题解

标签：frac 题解 sum ZJOI2014 fg jb

容易发现：

\[E_i=\sum_{j=1}^{i-1}\frac{q_j}{(i-j)^2}-\sum_{j=i+1}^n\frac{q_j}{(i-j)^2} \]

不妨设 \(a_i=q_i,b_i=\dfrac 1{i^2}\)：

\[E_i=\sum_{j=1}^{i-1}a_jb_{i-j}-\sum_{j=1}^{n-i}a_jb_{j-i} \]

发现前半部分就是多项式乘法，后半部分与 [BZOJ2194] 一致。直接 FFT 干过去即可。

时间复杂度 \(O(n\log n)\)。

#include<bits/stdc++.h>
#define stp fixed<<setprecision(3)
using namespace std;
const int N=3e5+5;
const double pi=acos(-1);
struct comn{double a,b;};
struct dft{comn fg[N];}f,g,h;
int n,m,rev[N],k,mx=1;
comn operator+(comn x,comn y){
    return {x.a+y.a,x.b+y.b};
}comn operator-(comn x,comn y){
    return {x.a-y.a,x.b-y.b};
}comn operator*(comn x,comn y){
    return {x.a*y.a-x.b*y.b,x.b*y.a+x.a*y.b};
}void operator+=(comn &x,comn y){x=x+y;}
void operator*=(comn &x,comn y){x=x*y;}
void init(){
    for(int i=0;i<mx;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    cout<<"";
}void fft(comn *a,int n,int fl){
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    comn om={cos(pi),fl*sin(pi)},w={1,0};
    for(int i=1;i<n;i*=2,om={cos(pi/i),fl*sin(pi/i)})
        for(int j=0;j<n;j+=i*2,w={1,0})
            for(int l=j;l<j+i;l++){
                comn x=a[l],y=w*a[l+i];
                a[l]+=y,a[l+i]=x-y,w*=om;
            }
}int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0),cin>>n;
    while(mx<=n+n) mx*=2,k++;
    for(int i=1;i<=n;i++)
        cin>>f.fg[i].a,g.fg[i].a=1.0/i/i;
    for(int i=0;i<=n;i++)
        h.fg[n-i].a=f.fg[i].a;
    init(),fft(f.fg,mx,1);
    fft(g.fg,mx,1),fft(h.fg,mx,1);
    for(int i=0;i<mx;i++)
        f.fg[i]*=g.fg[i],g.fg[i]*=h.fg[i];
    fft(f.fg,mx,-1),fft(g.fg,mx,-1);
    for(int i=1;i<=n;i++)
        cout<<stp<<(f.fg[i].a-g.fg[n-i].a)/mx<<"\n";
    return 0;
}//fast fourier transform

标签：frac,题解,sum,ZJOI2014,fg,jb
From： https://www.cnblogs.com/chang-an-22-lyh/p/18678465/zjoi2014-li-tj