Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int bit_rev(int t,int n){
- int res=0;
- for (int i=0;i<n;i++) res|=(t>>(n-i-1)&1)<<i;
- return res;
- }
- void fft(cd *a,int n,int rev){
- int len=1<<n;
- static cd y[N*4];
- for (int i=0;i<len;i++) y[i]=a[bit_rev(i,n)];
- for (int d=1;d<len;d<<=1){
- cd wn=exp(cd(0,PI*rev/d));
- for (int k=0;k<len;k+=(d<<1)){
- cd w=cd(1,0);
- for (int i=k;i<k+d;i++,w*=wn){
- cd u=y[i],v=w*y[i+d];
- y[i]=u+v;
- y[i+d]=u-v;
- }
- }
- }
- if (rev==-1)
- for (int i=0;i<len;i++) y[i]/=len;
- for (int i=0;i<len;i++) a[i]=y[i];
- }
- void mul(int *a,int la,int *b,int lb,int *c,int &lc){
- int len=1,n=0;
- static cd t1[N*4],t2[N*4];
- for (;len<la*2 || len<lb*2;len<<=1,++n);
- for (int i=0;i<len;i++){
- t1[i]=cd(i<la ? a[i] : 0,0);
- t2[i]=cd(i<lb ? b[i] : 0,0);
- }
- fft(t1,n,1);
- fft(t2,n,1);
- for (int i=0;i<len;i++) t1[i]*=t2[i];
- fft(t1,n,-1);
- lc=len-1;
- for (int i=0;i<len;i++) c[i]=(int)(t1[i].real()+0.5);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement