真好用...

把系数相乘看成\((a*M+b)*(c*M+d)=a*c*M^2+(a*d+b*c)*M+b*d\)的形式,这样FFT的精度就够用了...

#include
    
     #include
     
      #include
      
       #define LL long longusing namespace std;#define double long doubleconst double pi=acos(-1);const int maxn=300004;int n,m,tt,M,re[maxn],ans[maxn];struct jz{    double x,y;    jz(double x=0,double y=0):x(x),y(y){}    jz operator+(const jz &b)const{return jz(x+b.x,y+b.y);}    jz operator-(const jz &b)const{return jz(x-b.x,y-b.y);}    jz operator*(const jz &b)const{return jz(x*b.x-y*b.y,x*b.y+y*b.x);}}a[maxn],b[maxn],c[maxn],d[maxn],A[maxn];void FFT(jz a[],int f){    for (int i=1;i<=n;i++) if (i
       
        >1]>>1)|((i&1)<<(l-1)));    FFT(a,1);FFT(b,1);FFT(c,1);FFT(d,1);    work(a,c,(LL)M*M%tt);work(b,d,1);    work(a,d,M%tt);work(b,c,M%tt);    for (int i=0;i<=m;i++) printf("%d ",ans[i]);    return 0;}