bzoj2179 FFT快速傅立叶
程序员文章站
2022-05-09 18:27:09
2179: FFT快速傅立叶
Time Limit:10 SecMemory Limit:259 MB
Submit:2372Solved:1182
[Submi...
2179: FFT快速傅立叶
Time Limit:10 SecMemory Limit:259 MBSubmit:2372Solved:1182
[Submit][Status][Discuss]
Description
给出两个n位10进制整数x和y,你需要计算x*y。Input
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。Output
输出一行,即x*y的结果。Sample Input
13
4
Sample Output
12数据范围:
n<=60000
HINT
Source
#include #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define maxn 200000 using namespace std; const double pi=acos(-1.0); int n,m,len,rev[maxn],ans[maxn]; char s[maxn]; struct cp { double x,y; inline cp operator +(cp a){return (cp){x+a.x,y+a.y};} inline cp operator -(cp a){return (cp){x-a.x,y-a.y};} inline cp operator *(cp a){return (cp){x*a.x-y*a.y,x*a.y+y*a.x};} }a[maxn],b[maxn],c[maxn]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void fft(cp *x,int n,int flag) { F(i,0,n-1) if (rev[i]>i) swap(x[rev[i]],x[i]); for(int m=2;m<=n;m<<=1) { cp wn=(cp){cos(2.0*pi/m*flag),sin(2.0*pi/m*flag)}; for(int i=0;i>1; F(j,0,mid-1) { cp u=x[i+j],v=x[i+j+mid]*w; x[i+j]=u+v;x[i+j+mid]=u-v; w=w*wn; } } } } int main() { n=read(); scanf("%s",s); F(i,0,n-1) a[i].x=s[n-1-i]-'0'; scanf("%s",s); F(i,0,n-1) b[i].x=s[n-1-i]-'0'; m=1;n=2*n-1; while (m<=n) m<<=1,len++;n=m; F(i,0,n-1) { int t=i,ret=0; F(j,1,len) ret<<=1,ret|=t&1,t>>=1; rev[i]=ret; } fft(a,n,1);fft(b,n,1); F(i,0,n-1) c[i]=a[i]*b[i]; fft(c,n,-1); F(i,0,n-1) ans[i]=(c[i].x/n)+0.5; F(i,0,n-1) ans[i+1]+=ans[i]/10,ans[i]%=10; n++; while (!ans[n]&&n) n--; D(i,n,0) putchar(ans[i]+'0'); return 0; }