介绍

这个算法干什么？——快速的计算多项式乘法

这个算法时间复杂度是多少——O(NlogN)

怎么搞？

一些定义

[ ext{多项式};A(x) = sum_{i=1}^{N}a_ix^i ]

[ ext{多项式A和B的乘积C};C(x) = sum_{i=1}^{2 imes N}c_i imes x^i ]

[其中c_k=sum_{i+j=i,0 leq i,j < n}a_i imes b_j imes x^k ]

[ ext{(虚数单位)} i = sqrt{-1} ]

[ ext{N次单位根}omega_n^j = e^{frac{2ijpi}{n}}=(omega_n)^j ]

[w_n=e^{frac{2ipi}{n}}{} ]

接下来说在怎么fft

引理

[(omega_n^i)^2 ext{所构成的集合}=omega_{frac{n}{2}}^i ]

[ ext{证明：};;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ]

[ ext{带入定义易证} ]

坑以后填

#include<complex>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std ;

#define complexs complex<double>
#define N 2621450
const double Pi = acos(-1) ;
int limit = 1 ;
int r[N] ;

void fft(complexs* A, int type) {
    for (int i = 0; i < limit; i++)
        if (i < r[i]) swap(A[i], A[r[i]]);
    for (int mid = 1; mid < limit; mid <<= 1) {
        complexs Wn( cos(Pi / mid) , type * sin(Pi / mid) ); 
        for (int R = mid << 1, j = 0; j <limit; j += R) { 
            complexs w(1, 0); 
            for (int k = 0; k < mid; k++, w = w * Wn) {
                complexs x = A[j + k], y = w * A[j + mid + k];
                A[j + k] = x + y;
                A[j + mid + k] = x - y;
            }
        }
    }
}
complexs A[N],B[N] ;
int main(){
	int n,m,l=0 ; scanf("%d%d",&n,&m) ;
	for(limit=1;limit<=n+m;limit<<=1) ++l;
	for (int i = 0; i < limit; i++) 
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)) ;
	int x ;
	for(int i=0;i<=n;++i) {scanf("%d",&x) ; A[i]=complexs(x,0) ;}
	for(int i=0;i<=m;++i) {scanf("%d",&x) ; B[i]=complexs(x,0) ;}
	fft(A,1) ; fft(B,1) ;
	for(int i=0;i<limit;++i) A[i] = A[i]*B[i] ;
	fft(A,-1) ;
	for(int i=0;i<=n+m;++i){
		printf("%d ",int(A[i].real()/limit+0.5)) ;
	}
	puts("") ;
	return 0 ;
}