JZYZOJ 2041 快速数论变换 NTT 多项式

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

https://blog.csdn.net/ggn_2015/article/details/68922404 代码

https://blog.csdn.net/zz_1215/article/details/40430041 证明

这道题里只用快速幂就好了，抄的代码用的exgcd求的逆元，所以我也用的exgcd（权当复习了，exgcd倒推回去的时候记着只需要联立等式，每次自己推exgcd都会想太多……），其实费马小定理求逆元更方便啊，提供代码的人怎么肥四。

NTT和FFT差不多但是因为是在mod意义下的所以求的单位复根不是很一样（具体见证明和代码），其他地方除了需要mod一下都差不多。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<vector>

 #include<complex>

 using namespace std;

 #define LL long long

 const int maxn=;

 LL ans[maxn]={},p;

 LL a[maxn]={},b[maxn]={};

 int rev[maxn]={}; int s,bit;

 void exgcd(LL aa,LL bb,LL &x,LL &y){

     if(!bb){x=;y=;return;}

     exgcd(bb,aa%bb,x,y);

     LL z=x;

     x=y;y=z-((int)(aa/bb))*y;

 }

 inline LL getit(LL aa,LL bb){

     LL x,y; exgcd(aa,bb,x,y);

     x%=bb; while(x<)x+=bb;

     return x;

 }

 inline LL getpow(LL x,LL k){

     if(k<){k=-k; x=getit(x,p);}

     LL z=;

     while(k){

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

         x=(x*x)%p;

         k>>=;

     }

     return z;

 }

 inline void getrev(){ for(int i=;i<s;i++)rev[i]=((rev[i>>]>>)|((i&)<<(bit-))); }

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

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

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

         LL w=getpow(,dft*(p-)/(step*));

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

             LL z=;

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

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

                 c[j]=(x+y)%p;

                 c[j+step]=((x-y)%p+p)%p;

                 z=(z*w)%p;

             }

         }

     }

     if(dft==-){

         LL nn=getit(n,p);

         for(int i=;i<n;i++)c[i]=(c[i]*nn)%p;

     }

 }

 int main(){

     //cd cle(0,0);Pi=2.0*acos(0.0);

     int l1,l2;p=;

     while(~scanf("%d%d",&l1,&l2)){

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(ans,,sizeof(ans));

         memset(rev,,sizeof(rev));

         for(int i=;i<l1;i++)scanf("%lld",&a[i]);

         for(int i=;i<l2;i++)scanf("%lld",&b[i]);

         int n=l1+l2-;

         bit=;s=; for(;s<n;++bit)s<<=;

         getrev();

         fft(a,s,);fft(b,s,);

         for(int i=;i<s;i++)a[i]=(a[i]*b[i])%p;

         fft(a,s,-);

         for(int i=;i<n;i++)printf("%d ",a[i]);

         printf("\n");

     }

     return ;

 }