FFT&hash

1.FFT常看常新啊，比如突然发现complex比手写快!
注意实部和虚部的函数分别是real()和imag()

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define dow(i,j,k) for(int i=(j);i>=(k);--i)
#define pr pair
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define Complex complex<double> 
inline int read(int &x) {
	x=0;int ff=1;char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') ff=-1;ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;ch=getchar();
	}
	x*=ff;
	return x;
}
void write(int x) {
  if (x > 9)write(x / 10);
  putchar((x % 10) + '0');
}
//struct Complex 感觉不如std::complex<double>...速度 
//{
//    double x, y;
//    Complex (double x = 0, double y = 0) : x(x), y(y) { }
//};
//Complex operator * (const Complex &J, const Complex & Q) {
//    //模长相乘，幅度相加
//    return Complex(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);
//}
//Complex operator - (const Complex & J, const Complex & Q) {
//    return Complex(J.x - Q.x, J.y - Q.y);
//}
//Complex operator + (const Complex & J,const Complex & Q) {
//    return Complex(J.x + Q.x, J.y + Q.y);
//}
int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a>b?b:a;}
int exgcd(int a,int b,int&x,int&y) {
	if(b==0) {x=1,y=0 ;return a ;} 
	else {int r=exgcd(b,a%b,x,y);int t=x ;x=y ;y=t-a/b*y ;return r ;}
}
int fpow(int x,int y) { 
	int ans=1;int base=x;
	while(y) {
		if(y&1)ans=ans*base;
		y/=2;base=base*base;
	}
	return ans;
}
int mod=1e9+7;
const int maxn=4000301;
int die[maxn]; const double PI=acos(-1);
void FFT(int lim,Complex*a,double t){
	
	if(lim==1){
		return ;
	}
	for(int i=0;i<lim;i++){
		if(i<die[i])
		swap(a[i],a[die[i]]);
	}
	for(int mid=1;mid<lim;mid*=2){
		Complex wn=Complex(cos(PI/mid),t*sin(PI/mid)); 
		
		// 对于长度为2*mid的区间，从mid合并.f(w_n^k)=f1(w_n^2k)+-w_n^k*f2(w_n^2k)=f(w_n^k)=f1(w_n/2^k)+-w_n^k*f2(w_n/2^k) 
		for(int st=0;st<lim;st+=(mid<<1)){ //枚举用于合并新区间的点 
			Complex w=Complex(1,0);
			for(int k=0;k<mid;k++,w=w*wn){
				Complex x=a[st+k];
				Complex y=w*a[st+k+mid];
				a[st+k]=x+y;
				a[st+k+mid]=x-y;
			} 
		}
	}
	if(t<0){
		rep(i,0,lim-1){
			a[i]/=lim;
		}
	}	
}
Complex b[maxn],a[maxn];int n,m;
signed main() {
	
	//freopen("data.in","r",stdin);
	//freopen("T1.out","w",stdout);
	read(n);read(m);
	int lim=1;//一个n次多项式需要n+1个点,w_n的n为n+1 
	int cont=0;
	int x;
	rep(i,0,n){
		read(x);
		a[i]=Complex(x,0);
	}
	rep(i,0,m){
		read(x);
		a[i]+=Complex(0,x);
	}
	while(lim<=2*max(n,m)){
		lim<<=1;
		cont++; 
	}
	rep(i,0,lim-1){
		if(cont)
		die[i]=(die[(i>>1)]>>1)|((i&1)<<(cont-1));
	}
	FFT(lim,a,1.0);
//	FFT(lim,b,1.0); FFT是把系数变点值，或者给虚部乘上-1来把点值变系数，所以在卷实数系数时可以把第二个多项式放在虚部然后按照式子把f^2的虚部除以二 
	rep(i,0,lim-1){//这里不能是n+m，必须是lim 你本质上是在对一个lim项的多项式做变换,需要lim个点
		a[i]=a[i]*a[i];
	}
	FFT(lim,a,-1.0);

	rep(i,0,n+m){
		
		cout<<(int)(a[i].imag()/2+0.5)<<" ";//四舍五入就是很对，不懂
	}
	 
	return 0;
}
/*
5 5
1 7 4 0 9 4 
8 8 2 4 5 5 
*/

//感觉可以用这个来哈希字符串
for(char c : __TIME__  __TIMESTAMP__) {
		x += c, x ^= x << 13, x ^= x >> 7, x ^= x << 17;
	}