2179: FFT快速傅立葉

Time Limit:?10 Sec??Memory Limit:?259 MB
Submit:?3108??Solved:?1599
[Submit][Status][Discuss]

Description

給出兩個n位10進制整數x和y，你需要計算x*y。

Input

第一行一個正整數n。 第二行描述一個位數為n的正整數x。 第三行描述一個位數為n的正整數y。 數據范圍：
n<=60000

---

扔個模板 注意讀入字符轉換成系數 系數轉換成整數 #include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <cmath> using namespace std; const int N=3e5+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } const double PI=acos(-1); struct Vector{double x,y;Vector(double a=0,double b=0):x(a),y(b){} }; typedef Vector CD; Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);} Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);} Vector operator *(Vector a,Vector b){return Vector(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} Vector conj(Vector a){return Vector(a.x,-a.y);}struct FastFourierTransform{int n,rev[N];CD omega[N],omegaInv[N];void ini(int m){n=1;while(n<m) n<<=1;for(int k=0;k<n;k++) omega[k]=CD(cos(2*PI/n*k),sin(2*PI/n*k)),omegaInv[k]=conj(omega[k]);int k=0;while((1<<k)<n) k++;for(int i=0;i<n;i++){int t=0;for(int j=0;j<k;j++) if(i&(1<<j)) t|=(1<<(k-j-1));rev[i]=t;}}void transform(CD *a,CD *omega){for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int l=2;l<=n;l<<=1){int m=l>>1;for(CD *p=a;p!=a+n;p+=l)for(int k=0;k<m;k++){CD t=omega[n/l*k]*p[k+m];p[k+m]=p[k]-t;p[k]=p[k]+t;}}}void DFT(CD *a,int flag){if(flag==1) transform(a,omega);else{transform(a,omegaInv);for(int i=0;i<n;i++) a[i].x/=(double)n;}}void FFT(CD *a,CD *b,int m){ini(m);DFT(a,1);DFT(b,1);for(int i=0;i<n;i++) a[i]=a[i]*b[i];DFT(a,-1);} }fft;CD A[N],B[N]; int n,m,c[N]; char s1[N],s2[N]; int main(){freopen("in","r",stdin);n=read();m=n+n-1;scanf("%s%s",s1,s2);for(int i=0;i<n;i++) A[i].x=s1[n-i-1]-'0',B[i].x=s2[n-i-1]-'0';fft.FFT(A,B,m);for(int i=0;i<m;i++) c[i]=int(A[i].x+0.5);//printf("c %d\n",c[i]);for(int i=0;i<m;i++) c[i+1]+=c[i]/10,c[i]%=10;while(c[m]) m++;for(int i=m-1;i>=0;i--) printf("%d",c[i]);return 0; } FFT 1880ms #include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <cmath> using namespace std; const int N=3e5+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } const double PI=acos(-1); struct Vector{double x,y;Vector(double a=0,double b=0):x(a),y(b){} }; typedef Vector CD; Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);} Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);} Vector operator *(Vector a,Vector b){return Vector(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}struct FastFourierTransform{int n,rev[N];void ini(int m){n=1;while(n<m) n<<=1;int k=0;while((1<<k)<n) k++;for(int i=0;i<n;i++){int t=0;for(int j=0;j<k;j++) if(i&(1<<j)) t|=(1<<(k-j-1));rev[i]=t;}}void DFT(CD *a,int flag){for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int l=2;l<=n;l<<=1){int m=l>>1;CD wn(cos(2*PI/l),flag*sin(2*PI/l));for(CD *p=a;p!=a+n;p+=l){CD w(1,0);for(int k=0;k<m;k++){CD t=w*p[k+m];p[k+m]=p[k]-t;p[k]=p[k]+t;w=w*wn;}}}if(flag==-1) for(int i=0;i<n;i++) a[i].x/=n;}void FFT(CD *a,CD *b,int m){ini(m);DFT(a,1);DFT(b,1);for(int i=0;i<n;i++) a[i]=a[i]*b[i];DFT(a,-1);} }fft; CD A[N],B[N]; int n,m,c[N]; char s1[N],s2[N]; int main(){freopen("in","r",stdin);n=read();m=n+n-1;scanf("%s%s",s1,s2);for(int i=0;i<n;i++) A[i].x=s1[n-i-1]-'0',B[i].x=s2[n-i-1]-'0';fft.FFT(A,B,m);for(int i=0;i<m;i++) c[i]=int(A[i].x+0.5);//printf("c %d\n",c[i]);for(int i=0;i<m;i++) c[i+1]+=c[i]/10,c[i]%=10;while(c[m]) m++;for(int i=m-1;i>=0;i--) printf("%d",c[i]);return 0; } 遞推w的方法 FFT 1260ms

當然了，用NNT也可以，然而輸給了常數

#include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N=3e5+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } ll P=1004535809,MOD=P; ll Pow(ll a,ll b,ll MOD){ll ans=1;for(;b;b>>=1,a=a*a%MOD)if(b&1) ans=ans*a%MOD;return ans; } struct NumberTheoreticTransform{int n,rev[N];ll g;void ini(int m){n=1;while(n<m) n<<=1;int k=0;while((1<<k)<n) k++;for(int i=0;i<n;i++){int t=0;for(int j=0;j<k;j++) if(i&(1<<j)) t|=(1<<(k-j-1));rev[i]=t;}g=3;}void DFT(ll *a,int flag){for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int l=2;l<=n;l<<=1){int m=l>>1;ll wn=Pow(g,flag==1?(P-1)/l:P-1-(P-1)/l,P);for(ll *p=a;p!=a+n;p+=l){ll w=1;for(int k=0;k<m;k++){ll t=w*p[k+m]%P;p[k+m]=(p[k]-t+P)%P;p[k]=(p[k]+t)%P;w=w*wn%P;}}}if(flag==-1){ll inv=Pow(n,P-2,P);;for(int i=0;i<n;i++) a[i]=a[i]*inv%P;}}void MUL(ll *A,ll *B){DFT(A,1);DFT(B,1);for(int i=0;i<n;i++) A[i]=A[i]*B[i]%MOD;DFT(A,-1);} }fft; int n,m,c[N]; char s1[N],s2[N]; ll A[N],B[N]; int main(){freopen("in","r",stdin);n=read();m=n+n-1;scanf("%s%s",s1,s2);for(int i=0;i<n;i++) A[i]=s1[n-i-1]-'0',B[i]=s2[n-i-1]-'0';fft.ini(m);fft.MUL(A,B);for(int i=0;i<m;i++) c[i]=A[i];//printf("c %d\n",c[i]);for(int i=0;i<m;i++) c[i+1]+=c[i]/10,c[i]%=10;while(c[m]) m++;for(int i=m-1;i>=0;i--) printf("%d",c[i]); } NNT 3728ms

?

?

轉載于:https://www.cnblogs.com/candy99/p/6388403.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的BZOJ 2179 [快速傅里叶变换 高精度乘法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。