模板合集
1.数学
1.1 FFT（快速傅里叶变换）
1.1.1 递归版
#include
#define debug(x) printf("%d\n",x)
using namespace std;
typedef long long ll;
typedef pair 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