开年写的第一篇文章呀

首先祝大家新年快乐！

FFT理解请看算导+某Picks的博客

我反正是听ysy讲的。

我只会写复数版非递归。并不懂原根版。

代码并不长。

上来就是两题：BZOJ 2179 2194

# include <stdio.h>
# include <string.h>
# include <math.h>
# include <iostream>

using namespace std;

const double pi=acos(-1.0);

struct Complex {
	double r,i;
	Complex(double real=0.0,double image=0.0) {
		r=real;i=image;
	}
	Complex operator +(const Complex w) {
		return Complex(r+w.r,i+w.i);
	}
	Complex operator -(const Complex w) {
		return Complex(r-w.r,i-w.i);
	}
	Complex operator *(const Complex w) {
		return Complex(r*w.r-i*w.i,r*w.i+i*w.r);
	}
};
inline void brc(Complex *y,int l) {
	for (int i=1,j=l/2;i<l-1;++i) {
		if(i<j) swap(y[i],y[j]);
		int k=l/2;
		while(j>=k) {
			j-=k;
			k/=2;
		}
		if(j<k) j+=k;
	}
}

inline void fft(Complex *y, int l, double opt) {
	brc(y,l);
	for (int h=2;h<=l;h<<=1) {
		Complex wn(cos(opt*2*pi/h),sin(opt*2*pi/h));
		for (int j=0;j<l;j+=h) {
			Complex w(1,0);
			for (int k=j;k<j+h/2;++k) {
				Complex u=y[k],t=w*y[k+h/2];
				y[k]=u+t;
				y[k+h/2]=u-t;
				w=w*wn;
			}
		}
	}
	if(opt==-1.0)
		for (int i=0;i<l;++i) y[i].r/=l;
}
char s[330010];
Complex a[330010],b[330010];
int n,ss[330010];
int main() {
	scanf("%d",&n);
	scanf("%s",s);
	int A=1;
	while(A<n*2) A=A*2;
	for (int i=0;i<n;++i) a[i].r=s[n-i-1]-'0',a[i].i=0;
	for (int i=n;i<A;++i) a[i].r=a[i].i=0.0;
	scanf("%s",s);
	for (int i=0;i<n;++i) b[i].r=s[n-i-1]-'0',b[i].i=0;
	for (int i=n;i<A;++i) b[i].r=b[i].i=0.0;
	fft(a,A,1);
	fft(b,A,1);
	for (int i=0;i<A;++i) a[i]=a[i]*b[i];
	//for (int i=0;i<A;++i) printf("%lf %lf\n",a[i].r,a[i].i);
	fft(a,A,-1);
	for (int i=0;i<A;++i) ss[i]=a[i].r+0.5;
	for (int i=0;i<A;++i) {
		ss[i+1]+=ss[i]/10;
		ss[i]%=10;
	}
	A=2*n-1;
	while(ss[A]<=0 && A>0) --A;
	for (int i=A;i>=0;--i) printf("%d",ss[i]);
	printf("\n");
	return 0;
}

# include <stdio.h>
# include <string.h>
# include <math.h>
# include <iostream>

using namespace std;

const double pi=acos(-1.0);

struct Complex {
	double r,i;
	Complex(double real=0.0,double image=0.0) {
		r=real;i=image;
	}
	Complex operator +(const Complex w) {
		return Complex(r+w.r,i+w.i);
	}
	Complex operator -(const Complex w) {
		return Complex(r-w.r,i-w.i);
	}
	Complex operator *(const Complex w) {
		return Complex(r*w.r-i*w.i,r*w.i+i*w.r);
	}
};
inline void brc(Complex *y,int l) {
	for (int i=1,j=l/2;i<l-1;++i) {
		if(i<j) swap(y[i],y[j]);
		int k=l/2;
		while(j>=k) {
			j-=k;
			k/=2;
		}
		if(j<k) j+=k;
	}
}

inline void fft(Complex *y, int l, double opt) {
	brc(y,l);
	for (int h=2;h<=l;h<<=1) {
		Complex wn(cos(opt*2*pi/h),sin(opt*2*pi/h));
		for (int j=0;j<l;j+=h) {
			Complex w(1,0);
			for (int k=j;k<j+h/2;++k) {
				Complex u=y[k],t=w*y[k+h/2];
				y[k]=u+t;
				y[k+h/2]=u-t;
				w=w*wn;
			}
		}
	}
	if(opt==-1.0)
		for (int i=0;i<l;++i) y[i].r/=l;
}
char s[330010];
Complex a[330010],b[330010];
int n,ss[330010];
int main() {
	scanf("%d",&n);
	int A=1;
	while(A<n*2) A=A*2;
	for (int i=0;i<n;++i) {
		int ai,bi;scanf("%d %d",&ai,&bi);
		a[i].r=ai;
		b[n-i-1].r=bi;
		a[i].i=b[n-i-1].i=0.0;
	}
	fft(a,A,1);
	fft(b,A,1);
	for (int i=0;i<A;++i) a[i]=a[i]*b[i];
	//for (int i=0;i<A;++i) printf("%lf %lf\n",a[i].r,a[i].i);
	fft(a,A,-1);
	//for (int i=0;i<A;++i) ss[i]=a[i].r+0.5;
	//for (int i=0;i<A;++i) {
	//	ss[i+1]+=ss[i]/10;
	//	ss[i]%=10;
	//}
	//A=2*n-1;
	//while(ss[A]<=0 && A>0) --A;
	for (int i=n-1;i<=2*n-2;++i) printf("%.0lf\n",a[i].r+0.1);
	printf("\n");
	return 0;
}