hdu5958&uva7622题解

Dec 2, 2017 14:34 · 227 words · 2 minutes read 题解 hdu uva FFT 原根

让$c_{hk\mod p}=r(h,k)$,把下标对mod p的原根取个对数/指数就可以转化为卷积的形式。

一开始以为这道题要倍长其中一个多项式,后来发现其实不用,这样可以省掉一半的常数。

FFT真的是细节多,到处都要注意清零。

hdu上实在是卡常数卡不过去了,在uva上面A了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ele int
using namespace std;
#define maxn 300010
const double pi=acos(-1.0);
struct cd{
	double a,b;
};
inline cd operator+(cd a,cd b){
	return (cd){a.a+b.a,a.b+b.b};
}
inline cd& operator+=(cd&a,cd b){
	return a=a+b;
}
inline cd operator-(cd a,cd b){
	return (cd){a.a-b.a,a.b-b.b};
}
inline cd& operator-=(cd&a,cd b){
	return a=a-b;
}
inline cd operator*(cd a,cd b){
	return (cd){a.a*b.a-a.b*b.b,a.b*b.a+a.a*b.b};
}
inline cd& operator*=(cd&a,cd b){
	return a=a*b;
}
ele n,g,f[maxn];
double a[maxn],b[maxn];
cd a1[maxn],c[maxn],t1[maxn],t2[maxn];
inline void FFT(ele K,ele n,cd *a,cd *y){
	static ele f[maxn];
	f[0]=0; y[0]=a[0];
	for (int i=1; i<n; ++i){
		f[i]=f[i>>1]>>1;
		if (i&1) f[i]+=n>>1;
		y[i]=a[f[i]];
	}
	for (int p=1; p<n; p<<=1){
		cd o=(cd){cos(pi/p*K),sin(pi/p*K)};
		for (int i=0; i<n; i+=(p<<1)){
			cd o1=(cd){1,0};
			for (int j=i; j<i+p; ++j,o1*=o){
				cd u=y[j],v=y[j+p]*o1;
				y[j]=u+v;
				y[j+p]=u-v;
			}
		}
	}
	if (!~K) for (int i=0; i<n; ++i) y[i].a/=n,y[i].b/=n;
}
inline double getr(ele i){
	double t=sin(2*pi*i/n);
	return pow(2.0,t*t*t);
}
int main(){
	while (~scanf("%d",&n)){
		memset(a,0,sizeof(a));
		for (int i=0; i<n; ++i) scanf("%lf",a+i);
		g=(n==103)?5:2;
		f[0]=1;
		for (int i=0; i<n-1; f[i+1]=f[i]*g%n,++i)
			a1[n-2-i]=(cd){a[f[i]],0};
		memset(c,0,sizeof(c));
		for (int i=0; i<n-1; ++i)
			c[i]=(cd){getr(f[i]),0};
		ele tmp=1;
		while (tmp<n*2) tmp<<=1;
		FFT(1,tmp,a1,t1); FFT(1,tmp,c,t2);
		for (int i=0; i<tmp; ++i) t1[i]*=t2[i];
		FFT(-1,tmp,t1,c);
		for (int i=0; i<n-1; ++i){
			ele t=n-2+i;
			b[f[i]]=c[t].a;
			if (t>=n-1) b[f[i]]+=c[t-n+1].a;
		}
		b[0]=0;
		for (int i=0; i<n; ++i) b[0]+=a[i];
		for (int i=1; i<n; ++i) b[i]+=a[0];
		for (int i=0; i<n; ++i) printf("%.3lf ",(fabs(b[i])>1e-6)?b[i]:0);
		puts("");
	}
	return 0;
}