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

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

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<vector>
 7 #include<complex>
 8 using namespace std;
 9 #define LL long long
10 const int maxn=280010;
11 LL ans[maxn]={},p;
12 LL a[maxn]={},b[maxn]={};
13 int rev[maxn]={}; int s,bit;
14 void exgcd(LL aa,LL bb,LL &x,LL &y){
15     if(!bb){x=1;y=0;return;}
16     exgcd(bb,aa%bb,x,y);
17     LL z=x;
18     x=y;y=z-((int)(aa/bb))*y;
19 }
20 inline LL getit(LL aa,LL bb){
21     LL x,y; exgcd(aa,bb,x,y);
22     x%=bb; while(x<0)x+=bb;
23     return x;
24 }
25 inline LL getpow(LL x,LL k){
26     if(k<0){k=-k; x=getit(x,p);}
27     LL z=1;
28     while(k){
29         if(k&1)z=(z*x)%p;
30         x=(x*x)%p;
31         k>>=1;
32     }
33     return z;
34 }
35 inline void getrev(){ for(int i=0;i<s;i++)rev[i]=((rev[i>>1]>>1)|((i&1)<<(bit-1))); }
36 inline void fft(LL *c,int n,int dft){
37     for(int i=1;i<=s;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);
38     for(int step=1;step<n;step<<=1){
39         LL w=getpow(3,dft*(p-1)/(step*2));
40         for(int i=0;i<n;i+=step<<1){
41             LL z=1;
42             for(int j=i;j<i+step;j++){
43                 LL x=c[j],y=(c[j+step]*z)%p;
44                 c[j]=(x+y)%p;
45                 c[j+step]=((x-y)%p+p)%p;
46                 z=(z*w)%p;
47             }
48         }
49     }
50     if(dft==-1){
51         LL nn=getit(n,p);
52         for(int i=0;i<n;i++)c[i]=(c[i]*nn)%p;
53     }
54 }
55 int main(){
56     //cd cle(0,0);Pi=2.0*acos(0.0);
57     int l1,l2;p=998244353;
58     while(~scanf("%d%d",&l1,&l2)){
59         memset(a,0,sizeof(a));
60         memset(b,0,sizeof(b));
61         memset(ans,0,sizeof(ans));
62         memset(rev,0,sizeof(rev));
63         for(int i=0;i<l1;i++)scanf("%lld",&a[i]);
64         for(int i=0;i<l2;i++)scanf("%lld",&b[i]);
65         int n=l1+l2-1;
66         bit=1;s=2; for(;s<n;++bit)s<<=1;
67         getrev();
68         fft(a,s,1);fft(b,s,1);
69         for(int i=0;i<s;i++)a[i]=(a[i]*b[i])%p;
70         fft(a,s,-1);
71         for(int i=0;i<n;i++)printf("%d ",a[i]);
72         printf("
");
73     }
74     return 0;
75 }

View Code