BZOJ 3527 [Zjoi2014]力

乘进去之后是裸的卷积，FFT解决，卷积题熟练度++

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define sqr(x) ((x)*(x))
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////

const int maxn=1048576;
const double pi=3.1415926535897932384626433832795028841971693993751058209749446;
int r[maxn],n,m,l,nn;
struct cp
{
    double x,y;
    cp(double a=0,double b=0):x(a),y(b){}
    cp operator+(cp a){return cp(x+a.x,y+a.y);}
    cp operator-(cp a){return cp(x-a.x,y-a.y);}
    cp operator*(cp a){return cp(xa.x-ya.y,xa.y+ya.x);}
    cp operator/(int a){return cp(x/a,y/a);}
}A[maxn],B[maxn],AA[maxn];
inline void swap(cp &a,cp &b){cp t=a;a=b;b=t;}
void FFT(cp *a,int n,int op)
{
    rep(i,0,n-1) if (i<r[i]) swap(a[i],a[r[i]]);
    for (int i=1;i<n;i<<=1)
    {
        cp wn(cos(pi/i),sin(pi/i)op);
        for (int j=0;j<n;j+=i<<1)
        {
            cp w(1,0);
            for (int k=0;k<i;k++,w=wwn)
            {
                cp x=a[j+k],y=a[i+j+k]*w;
                a[j+k]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
}
int main()
{
    read(n);
    m=n;
    nn=n;
    rep(i,0,n-1) scanf("%lf",&A[i].x);
    rep(i,0,n-1) AA[n-i-1].x=A[i].x;
    rep(i,1,n-1) B[i].x=(double)1/(i)/(i);
m+=n-2;
for (l=0,n=1;n&lt;=m;n&lt;&lt;=1,++l);
rep(i,0,n-1) r[i]=(r[i&gt;&gt;1]&gt;&gt;1)|((i&amp;1)&lt;&lt;(l-1));
FFT(A,n,1);FFT(B,n,1);
rep(i,0,n-1) A[i]=B[i]*A[i];
FFT(A,n,-1);
rep(i,0,n-1) A[i].x=A[i].x/n;

FFT(AA,n,1);
rep(i,0,n-1) AA[i]=B[i]*AA[i];
FFT(AA,n,-1);
rep(i,0,n-1) AA[i].x=AA[i].x/n;

rep(i,0,nn-1) printf(&quot;%lf\n&quot;,-AA[nn-i-1].x+A[i].x);
return 0;
}