bzoj2179 FFT快速傅立葉

NO IMAGE

Description


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

n<=60000

Solution


放一波板子,計算卷積利器,一個極佳blog
大概就是把係數表示法變成點值表示法,這樣就直接掃一遍乘起來即可。可以理解成用一個函式去擬合之類的,對於一個n次的多項式我們需要取n-1個點
這裡實際上利用了複數的各種神奇性質使得我們可以取值插值用分治做到nlogn,但是由於需要補全高位上的0項使得常數巨大,而且我打的還是遞迴-_-||

Code


#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <complex>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
using namespace std;
typedef complex<double> com;
const double Pi=3.14159265358979323846264338327950288;
const int N=131082;
char sta[N],stb[N];
com a[N],b[N];
int prt[N];
int read() {
int x=0,v=1; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10 ch-'0',ch=getchar());
return x*v;
}
void FFT(com *c,int len,int f) {
if (len==1) return ;
com wn(cos(2.0*Pi/len),sin(f*2.0*Pi/len)),w(1,0),t;
com c1[len/2],c2[len/2];
rep(i,0,len/2-1) {
c1[i]=c[i*2 0];
c2[i]=c[i*2 1];
}
FFT(c1,len/2,f); FFT(c2,len/2,f);
for (int i=0;i<len/2;i  ,w*=wn) {
t=c2[i]*w;
c[i]=c1[i] t;
c[i len/2]=c1[i]-t;
}
}
int main(void) {
scanf("%*d%s%s",sta,stb);
int n=strlen(sta)-1,m=strlen(stb)-1;
rep(i,0,n) a[i]=sta[i]-'0';
rep(i,0,m) b[i]=stb[i]-'0';
m =n; for (n=1;n<=m;n<<=1);
FFT(a,n,1); FFT(b,n,1);
rep(i,0,n) a[i]*=b[i];
FFT(a,n,-1);
int tmp=0;
drp(i,m,0) {
prt[i]=(tmp (int)(a[i].real()/n 0.5))%10;
tmp=(tmp (int)(a[i].real()/n 0.5))/10;
}
if (tmp) printf("%d",tmp);
rep(i,0,m) printf("%d",prt[i]);
return 0;
}