[ZJOJ2014] 力解题报告 (FFT)

题目链接：

https://www.luogu.org/problemnew/show/P3338

题目：

给出$n$个数$q_i$，令$F_j=\sum_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum_{i>j}\frac{q_iq_j}{(i-j)^2}$，$E_i=\frac{F_i}{q_i}$，求$E_i$

题解：

显然$E_j=\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i}{(i-j)^2}$

不妨设$G_i=\frac{1}{i^2},G_0=0$,$T_i=q_i,T_0=0$

那么$E_j=\sum_{i=1}^{j-1}T_iG_{i-j}-\sum_{i=j+1}^{n}T_iG_{i-j}$

=$\sum_{i=0}^{j}T_iG_{i-j}-\sum_{i=j+1}^{n}T_iG_{i-j}$

显然减号前的部分是一个卷积的形式，是把$T$和$G$卷起来的第$i$项

设$W_i=T_{n-i+1}(1<=i<=n),W_0=0$

减号后的$=\sum_{i=j+1}^nW_{n-i+1}G_{i-j}$

$=\sum_{i=1}^{n-j}W_iG_{n+1-i-j}$

=$\sum_{i=0}^{n-j+1}W_iG_{n+1-i-j}$

这显然也是一个卷积的形式，是把$W$和$G$卷起来的第$n+1-j$项

$E_j=\sum_{i=0}^{j}T_iG_{i-j}-\sum_{i=0}^{n-j+1}W_iG_{n+1-i-j}$

代码：

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

typedef double db;

const int N=4e5+;

const double pi=acos(-1.0);

struct complex

{

    double x,y;

    complex (double xx=,double yy=) {x=xx;y=yy;}

}A[N],B[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 n;

int r[N<<];

void fft(int limit,complex *a,int type)

{

    for (int i=;i<limit;i++) if (i<r[i]) swap(a[i],a[r[i]]);

    for (int len=;len<limit;len<<=)

    {

        complex wn=complex(cos(pi/len),type*sin(pi/len));

        for (int k=;k<limit;k+=(len<<))

        {

            complex w=complex(,);

            for (int l=;l<len;l++,w=w*wn)

            {

                complex Nx=a[k+l],Ny=w*a[k+l+len];

                a[k+l]=Nx+Ny;

                a[k+l+len]=Nx-Ny;

            }

        }

    }

}

void work(db *a,db *b,db *c)

{

    int limit=,l=;

    while (limit<n+n) limit<<=,++l;

    for (int i=;i<=limit;i++) r[i]=(r[i>>]>>)|((i&)<<(l-));

    for (int i=;i<=limit;i++) A[i].x=a[i],B[i].x=b[i],A[i].y=,B[i].y=;

    fft(limit,A,);fft(limit,B,);

    for (int i=;i<=limit;i++) A[i]=A[i]*B[i];

    fft(limit,A,-);

    for (int i=;i<=limit;i++) c[i]=A[i].x/limit;

}

db q[N],p[N],f[N],a[N],b[N];

int main()

{

    scanf("%d",&n);

    for (int i=;i<=n;i++)

    {

        scanf("%lf",&q[i]);

        p[i]=q[i];

        f[i]=(db)(1.0/i/i);

    }

    reverse(p+,p++n);

    f[]=;q[]=;p[]=;

    work(q,f,a);

    work(p,f,b);

    for (int i=;i<=n;i++) printf("%lf\n",a[i]-b[n-i+]);

    return ;

}

巴特西

[ZJOJ2014] 力解题报告 (FFT)

题目链接：

题目：

题解：

代码：

最新文章

热门文章

巴特西

[ZJOJ2014] 力 解题报告 (FFT)

题目链接：

题目：

题解：

代码：

最新文章

热门文章

[ZJOJ2014] 力解题报告 (FFT)