模板合集

1.数学

1.1 FFT（快速傅里叶变换）

1.1.1 递归版 

View Code

#include<bits/stdc++.h>
#define debug(x) printf("%d\n",x)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int M=4e6+5;
const double pi=acos(-1.0);
int n,m;
struct node {
	double x,y;
}a[M],b[M];
node operator + (node A,node B) {return (node){A.x+B.x,A.y+B.y};}
node operator - (node A,node B) {return (node){A.x-B.x,A.y-B.y};}
node operator * (node A,node B) {return (node){A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x};}
node operator / (node A,node B) {return (node){(A.x*B.x+A.y*B.y)/(B.x*B.x+B.y*B.y),(A.y*B.x-A.x*B.y)/(B.x*B.x+B.y*B.y)};}
void FFT(int x,node *a,int type) {
	if(x==1) return;
	node a1[x/2+1],a2[x/2+1];
	for(int i=0;i<=x;i+=2) a1[i/2]=a[i],a2[i/2]=a[i+1];
	FFT(x/2,a1,type); FFT(x/2,a2,type);
	node Wn={cos(2.0*pi/x),type*sin(2.0*pi/x)},Wnk={1,0};
	for(int k=0;k<x/2;k++) {
		a[k]=a1[k]+Wnk*a2[k];
		a[k+x/2]=a1[k]-Wnk*a2[k];
		Wnk=Wnk*Wn;
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++) scanf("%lf",&a[i].x);
	for(int i=0;i<=m;i++) scanf("%lf",&b[i].x);
	int x=1; while(x<=n+m) x<<=1;
	FFT(x,a,1); FFT(x,b,1);
	for(int i=0;i<=x;i++) a[i]=a[i]*b[i];
	FFT(x,a,-1);
	for(int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].x/x+0.5));
	return 0;
}