JZYZOJ 2043 多项式除法和取余 NTT 多项式

http://172.20.6.3/Problem_Show.asp?id=2043

最开始用了FFT，交上去全tle和wa了（tle的比较多），测了一组数据发现求逆元的过程爆double了（毕竟系数的指数幂也是指数增长的，科学计数法也撑不住）。

然后问了出题人，发现出题人忘了给用来%的P（想用钢丝球刷出题人QnQ），所以其实是ntt，改完ntt加了个快读a了。

题解：http://blog.miskcoo.com/2015/05/polynomial-division

依然是推式子，系数反转求也是很神奇。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<complex>

 using namespace std;

 #define LL long long

 const int maxn=;

 const LL P=(LL)**(<<)+;

 LL a[maxn],b[maxn],e[maxn],h[maxn],zz[][maxn];

 int bel[maxn]={},s,bt,tot=;

 inline void getit(){ for(int i=;i<s;++i)bel[i]=((bel[i>>]>>)|((i&)<<(bt-))); }

 LL mpow(LL x,LL k){

     if(k<){x=mpow(x,P-);k=-k;}

     LL z=;

     while(k){

         if(k&)z=(z*x)%P;

         x=(x*x)%P;k/=;

     }

     return z;

 }

 inline void fft(LL * c,int n,int dft){

     for(int i=;i<n;++i)if(bel[i]>i)swap(c[i],c[bel[i]]);

     for(int step=;step<n;step<<=){

         LL w=mpow(,((P-)/(step<<))*dft);

         for(int j=;j<n;j+=(step<<)){

             LL z=;

             for(int i=j;i<j+step;++i){

                 LL x=c[i],y=(c[i+step]*z)%P;

                 c[i]=(x+y)%P;c[i+step]=((x-y)%P+P)%P;

                 z=(z*w)%P;

             }

         }

     }

     if(dft==-){

         LL nm=mpow(n,P-);

         for(int i=;i<n;++i)c[i]=(c[i]*nm)%P;

     }

 }

 void dofft(LL *c,LL *d,int x,int y){

     int n=x+y-;s=;bt=;

     for(;s<n;++bt)s<<=;getit();

     fft(c,s,);fft(d,s,);

     for(int i=;i<s;++i)c[i]=(c[i]*d[i])%P;

     fft(c,s,-);fft(d,s,-);

 }

 void doit(int n,int m){

     if(m==){ ++tot; zz[tot][]=mpow(b[],P-); return; }

     int siz=(m+)/; doit(n,siz); ++tot;

     for(int i=;i<siz;++i){zz[tot][i]=(zz[tot-][i]*)%P;e[i]=zz[tot-][i];}

     for(int i=;i<min(m,n);++i)h[i]=b[i];//cout<<zz[tot-1][0]<<m<<endl;

     dofft(zz[tot-],e,siz,siz);siz=siz+siz-;//cout<<zz[tot-1][0]<<m<<endl;

     dofft(zz[tot-],h,siz,min(m,n));

     for(int i=;i<m;++i)zz[tot][i]=((zz[tot][i]-zz[tot-][i])%P+P)%P;

     //for(int i=0;i<m;++i)cout<<zz[tot][i]<<' ';cout<<endl;

 }

 LL mread(){

     LL x=,f=; char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int main(){

     //freopen("a.in","r",stdin);

     int n,m;scanf("%d%d",&n,&m);

     for(int i=;i<n;++i){a[n-i-]=mread();a[n-i-]=(a[n-i-]%P+P)%P;}

     for(int i=;i<m;++i){b[m-i-]=mread();b[m-i-]=(b[m-i-]%P+P)%P;}

     doit(m,n-m+);

     dofft(zz[tot],a,n-m+,n);

     for(int i=n-m;i>=;--i){printf("%lld ",zz[tot][i]);}printf("\n");

     for(int i=n-m+;i<s;++i)zz[tot][i]=;

     for(int i=;i<=n-m;++i){if(i>=n-m-i)break;swap(zz[tot][i],zz[tot][n-m-i]);}

     for(int i=;i<n;++i){if(i>=n-i-)break;swap(a[i],a[n-i-]);}

     for(int i=;i<m;++i){if(i>=m-i-)break;swap(b[i],b[m-i-]);}

     dofft(b,zz[tot],m,n-m+);

     for(int i=;i<m-;++i){a[i]=((a[i]-b[i])%P+P)%P;}

     for(int i=;i<m-;++i){printf("%lld ",a[i]);}printf("\n");

     return ;

 }