@OceanEye7年前
05/21
13:46
先上几个好的教程
- 某不知名大佬的教程 简直良心治好了我一直没搞清楚的FFT:-D
- zky大佬的FFT教程
- kry大佬的板子:-D
[手动分割]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #define ll long long #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read(T &x) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 1<<22 int n,m; int pos[N]; int k,j; const double pi=acos(-1.0); struct comp { double r,i; comp(double _r=0,double _i=0){ r=_r; i=_i; } comp operator+(const comp&x) { return comp(r+x.r,i+x.i); } comp operator-(const comp&x) { return comp(r-x.r,i-x.i); } comp operator*(const comp&x) { return comp(r*x.r-i*x.i,r*x.i+i*x.r); } comp conj() {return comp(r,-i);} }a[N],b[N]; void fft(comp a[],int n,int t) { for(int i=1;i<n;i++) if(pos[i]>i) swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++) { int m=1<<d,m2=m<<1; double o=pi*2/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2) { comp w(1,0); for(int j=0;j<m;j++) { comp &A=a[i+j+m],&B=a[i+j],t=w*A; A=B-t; B=B+t; w=w*_w; } } } if(t==-1) For(i,0,n-1) a[i].r/=n; } int main() { freopen("BZOJ2179FFT.in","r",stdin); read(n); read(m); for(k=1;k<=n||k<=m;k<<=1); k<<=1; j=__builtin_ctz(k)-1; For(i,0,k-1) pos[i]=pos[i>>1]>>1|((i&1)<<j); // For(i,0,k-1) printf("%d\n",pos[i]); For(i,0,n) read(j),a[i].r=j; For(i,0,m) read(j),a[i].i=j; fft(a,k,1); For(i,0,k-1) { j=(k-i)&(k-1); b[i]=(a[i]*a[i]-(a[j]*a[j]).conj())*comp(0,-0.25); } fft(b,k,-1); For(i,0,n+m) printf("%d ",(int)(b[i].r+0.5)); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> #define ll long long #define db double #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } template <class T>void rd( T &x ) { cc=getchar(); while(!p(cc)) cc=getchar(); x=cc-'0'; } using namespace std; #define N 1<<17 const double pi=acos(-1.0); struct comp { double r,i; comp(double _r=0,double _i=0) { r=_r; i=_i; } comp operator+ (const comp &x) { return comp(r+x.r,i+x.i); } comp operator- (const comp &x) { return comp(r-x.r,i-x.i); } comp operator* (const comp &x) { return comp(r*x.r-i*x.i,r*x.i+i*x.r); } comp conj() { return comp(r,-i); } }a[N],b[N]; int n,k,j,pos[N]; ll c[N]; char na[N]; void fft(comp a[],int n,int t) { For(i,0,n-1) if(pos[i]>i) swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++) { int m=1<<d,m2=m<<1; double o=pi*2/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2) { comp w(1,0); for(j=0;j<m;j++) { comp &A=a[i+j+m],&B=a[i+j],t=A*w; A=B-t; B=B+t; w=w*_w; } } } if(t==-1) For(i,0,n-1) a[i].r/=n; } int main() { read(n); n--; for(k=1;k<=n;k<<=1); k<<=1; j=__builtin_ctz(k)-1; For(i,0,k-1) pos[i]=(pos[i>>1]>>1)|((i&1)<<j); For(i,0,n) rd(j),a[i].r=j; For(i,0,n) rd(j),a[i].i=j; fft(a,k,1); For(i,0,k-1) { j=(k-i)&(k-1); b[i]=(a[i]*a[i]-(a[j]*a[j]).conj())*comp(0,-0.25); } fft(b,k,-1); For(i,0,n*2) c[i]=(ll)(b[i].r+0.4); bool flag=false; int a=0,tot=0; for(int i=n*2;i>=0;i--) { a+=c[i]; na[tot++]=(char)(a%10); a/=10; } if(a) na[tot++]=(char)a; for(;tot;putchar(na[--tot]+'0')); return 0; } |
BZOJ2194
好像就是反过来？
挺裸的:-D
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 1<<21 const double pi=acos(-1.0); struct comp { double r,i; comp(double _r=0,double _i=0) { r=_r; i=_i; } comp operator+ (const comp &x) { return comp(r+x.r,i+x.i); } comp operator- (const comp &x) { return comp(r-x.r,i-x.i); } comp operator* (const comp &x) { return comp(r*x.r-i*x.i,r*x.i+i*x.r); } comp conj() { return comp(r,-i); } }a[N],b[N]; int k,j,n; int pos[N]; void fft(comp a[],int n,int t) { For(i,0,n-1) if(pos[i]>i) swap(a[i],a[pos[i]]); for(int k=0;(1<<k)<n;k++) { int m=1<<k,m2=m<<1; double o=2*pi/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2) { comp w(1,0); for(j=0;j<m;j++) { comp &A=a[i+j+m],&B=a[i+j],t=A*w; A=B-t; B=B+t; w=w*_w; } } } if(t==-1) For(i,0,n-1) a[i].r/=n; } int main() { read(n); n--; for(k=1;k<=n;k<<=1); k<<=1; j=__builtin_ctz(k)-1; For(i,0,k-1)pos[i]=(pos[i>>1]>>1)|((i&1)<<j); For(i,0,n){ read(j); a[i].r=j; read(j); a[n-i].i=j; } fft(a,k,1); For(i,0,k-1) { j=(k-1)&(k-i); b[i]=(a[i]*a[i]-(a[j]*a[j]).conj())*comp(0,-0.25); } fft(b,k,-1); for(int i=n;i<=n*2;i++) printf("%d\n",(int)(b[i].r+0.5)); return 0; } |
[代码施工中]