ZJOI2014力

ZJOI2014 力

题目大意

$$F_j=\sum_{i<j} \dfrac{q_i q_j}{(i-j)^2} - \sum _{i>j} \dfrac{q_i q_j}{(i-j)^2}$$

求$E_i=\dfrac{F_i}{q_i}$

化简$E_i$

$$\begin{aligned} E_j&=\dfrac{F_j}{q_j}\\ &=\dfrac{1}{q_j}\sum_{i<j} \dfrac{q_i q_j}{(i-j)^2} - \sum _{i>j} \dfrac{q_i q_j}{(i-j)^2}\\ &=\sum_{i<j} \dfrac{q_i}{(i-j)^2} - \sum _{i>j} \dfrac{q_i}{(i-j)^2}\\ &=\sum_{i=1}^{j-1} \dfrac{q_i}{(i-j)^2} - \sum _{i=j+1}^{n} \dfrac{q_i}{(i-j)^2} \end{aligned}$$

我们根据卷积的定义

$$C(n)=\sum _{i=0}^{n}F(i)\times G(n-i)$$

设 $F(x)=q_x$ , $G(x)=\dfrac{1}{x^2}$

原式化简为 $E{j}=\displaystyle\sum{i=1}^{j-1}F(i)\times G(j-i)-\displaystyle \sum _{i=j+1}^{n}F(i)\times G(i-j)$
前面那个便是 $F$ 卷 $G$

$$\displaystyle \sum _{i=j+1}^{n}F(i)\times G(i-j)$$

设$k=i-j$ 原式 $=\displaystyle \sum{k=1}^{n-j}F(k+j)G(k)$
翻转$F$后得到$h$,$h$ 满足 $h(i)=F(n-i)$ , 同时 $F(i)=h(n-i)$
原式 $=\displaystyle \sum{k=1}^{n-j}h(n-j-k)G(k)$
设 $t=n-j$
原式 $=\displaystyle \sum_{k=1}^{t}h(t-k)G(k)$
故 后面的是$h$ 卷 $G$
所以我们将前后分开算，也就是先把$F$ $G$ $h$ fft成点值表示
然后分别计算卷积后插值，就可以了！

#include<bits/stdc++.h>
using namespace std;
const int N=400000;
struct Complex
{
    double x,y;
}f[N],g[N],h[N];
Complex operator + (Complex a,Complex b)
{
    Complex c;
    c.x=a.x+b.x;
    c.y=a.y+b.y;
    return c;
}
Complex operator - (Complex a,Complex b)
{
    Complex c;
    c.x=a.x-b.x;
    c.y=a.y-b.y;
    return c;
}
Complex operator * (Complex a,Complex b)
{
    Complex c;
    c.x=a.x*b.x-a.y*b.y;
    c.y=a.x*b.y+a.y*b.x;
    return c;
}
const double pie=acos(-1);
int rev[N];
inline void fft(Complex *a,int lim,int flag)
{
    for(int i=1;i<lim;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int mid=1;mid<lim;mid=(mid<<1))
    {
        Complex wn;
        wn.x=cos(pie/double(mid));
        wn.y=1.0*flag*sin(pie/double(mid));
        for(int j=0;j<lim;j+=(mid<<1))
        {
            Complex w;
            w.x=1.0,w.y=0;
            for(int k=0;k<mid;k++,w=w*wn)
            {
                Complex x=a[k+j],y=w*a[k+j+mid];
                a[k+j]=x+y;
                a[k+j+mid]=x-y;
            }
        }
    }
    if(flag==-1)
        for(int i=0;i<lim;i++)
            a[i].x/=double(lim);
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf",&f[i].x);
    for(int i=0;i<=n;i++)
        g[i].x=f[n-i].x;
    for(int i=1;i<=n;i++) h[i].x=(1.0/(1.0*double(i)))/(double(i));
    int lim=1,len=0;
    while(lim<=2*(n)) lim<<=1,len++;
    for(int i=1;i<lim;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
    fft(f,lim,1);
    fft(g,lim,1);
    fft(h,lim,1);
    for(int i=0;i<lim;i++) f[i]=f[i]*h[i];
    for(int i=0;i<lim;i++) g[i]=g[i]*h[i];
    fft(f,lim,-1);
    fft(g,lim,-1);
    for(int i=1;i<=n;i++) printf("%.6lf\n",f[i].x-g[n-i].x);
    #ifdef _WIN32
    system("pause");
    #endif
}