FFT快速傅立叶 bzoj-2179

题目大意：给出两个n位10进制整数x和y，你需要计算x*y。

注释：$1\le n\le 6\times 10^4$。

想法：

$FFT$入门题。

$FFT$实现的就是多项式乘法，进而我们可以通过它优化卷积。

但是有一点：$FFT$优化的卷积是所有的都求出来而不能单独优化一次。

比如说：$c_i=\sum_{j=0}^i a_j\times b_{i-j}$。

$FFT$可以在$O(nlogn)$的时间内求出所有的$c$，但是不能只求一个。

附上$FFT$的模板：

typedef double db;const db pi=acos(-1);struct cp{	db x,y;	cp() {x=y=0;}	cp(db x_,db y_) {x=x_,y=y_;}	cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}	cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}	cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}};void fft(cp *a,int len,int flg){	int i,j,k,t;	cp w,wn,tmp;	for(i=k=0;i
     
      k) swap(a[i],a[k]);		for(j=len>>1;(k^=j)
      
       >=1);	}	for(k=2;k<=len;k<<=1)	{		t=k>>1;		wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k));		for(i=0;i

而这个题就是将每一位看成多项式的系数，然后用$FFT$算多项式乘法即可，注意进位。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 60010 using namespace std; typedef double db;char s1[N<<1],s2[N<<1];int ans[N<<2];const db pi=acos(-1);struct cp{	db x,y;	cp() {x=y=0;}	cp(db x_,db y_) {x=x_,y=y_;}	cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}	cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}	cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}}a[N<<2],b[N<<2];void fft(cp *a,int len,int flg){	int i,j,k,t;	cp tmp,w,wn;	for(i=k=0;i
          
           k) swap(a[i],a[k]); for(j=len>>1;(k^=j)
           
            >=1); } for(k=2;k<=len;k<<=1) { wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k)); t=k>>1; for(i=0;i
            
             > n ; int len=1; while(len<=(n<<1)) len<<=1; scanf("%s%s",s1,s2); for(int i=0;i