【HDU5958】New Signal Decomposition

  • 本文为博主原创，未经许可不得转载

我们要求$b_i=\sum_{j=0}^{P-1}a_j 2^{\sin^3{\frac{2\pi ij}{P}}}$，下标取离散对数化为加法：

$$b_{g^i(mod P)}=\sum_{j=0}^{P-1}a_{g^j (mod P)} 2^{\sin^3{\frac{2\pi g^{i+j}(mod P)}{P}}}$$

把$a$数组拧一下变成：（由欧拉定理，指数对$\phi(P)取模$）$$b_{g^i(mod P)}=\sum_{j=0}^{P-1}a_{g^{\phi(P)-j-1} (mod P)} 2^{\sin^3{\frac{2\pi g^{i+j}(mod P)}{P}}}$$

这样就成卷积了，答案贡献在$\phi(P)+i-1(mod \phi(P))$上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 300010
const double pi=acos(-1);
int P,G,g[MAXN],R[MAXN];double Ans[MAXN];
std::vector<int>fac;
struct complex{
	double r,v; 
	complex(double a=0,double b=0):r(a),v(b){}
	inline complex operator+(const complex &b){return complex(r+b.r,v+b.v);}
	inline complex operator-(const complex &b){return complex(r-b.r,v-b.v);}
	inline complex operator*(const complex &b){return complex(r*b.r-v*b.v,r*b.v+v*b.r);}
}a[MAXN],b[MAXN],c[MAXN],w[MAXN];
inline void swap(complex &a,complex &b){complex t(a);a=b;b=t;}
inline int Pow(int a,int b,int P){
	int ret=1;
	while(b){
		if(b&1) ret=ret*a%P;
		b>>=1; a=a*a%P;
	}return ret;
}
void FFT(complex *a,int H,int f){
	int L=(1<<H);
	for(int i=0;i<L;++i) if(i<R[i]) swap(a[i],a[R[i]]);
	for(int len=2;len<=L;len<<=1){
		int l=(len>>1); //complex wn(cos(pi/l),f*sin(pi/l));
		for(int i=1;i<l;++i) w[i]=w[i-1]*wn;
		for(int st=0;st<L;st+=len)for(int k=0;k<l;++k){
			complex x=a[st+k],y=w[k]*a[st+k+l];
			a[st+k]=x+y; a[st+k+l]=x-y;
		}
	}
	if(f==-1) for(int i=0;i<L;++i) a[i].r/=L;
}
int getG(int P){
	int phi=P-1; fac.clear();
	for(int i=2;i<=sqrt(phi);++i)if(phi%i==0){
		fac.push_back(i);
		fac.push_back(phi/i);
	}
	for(int i=2;i<P;++i){
		bool Flag=1;
		for(int j=0;j<fac.size();++j)
			if(Pow(i,phi/fac[j],P)==1) {Flag=0;break;}
		if(Flag) return i;
	}
}
void solve(){
	G=getG(P); g[0]=1; w[0]=1; int E=P-1;
	int L=1,H=0; while(L<P+P) L<<=1,++H;
	for(int i=0;i<L;++i) a[i]=b[i]=c[i]=Ans[i]=0;
	for(int i=0;i<P;++i) scanf("%lf",&a[i]);
	for(int i=1;i<P;++i) Ans[i]=a[0].r;
	for(int i=0;i<P;++i) Ans[0]+=a[i].r;
	for(int i=1;i<P;++i) g[i]=g[i-1]*G%P;
	for(int i=0;i<E;++i) b[i]=pow(2.0,pow(sin(2*pi*g[i]/P),3.0));
	for(int i=0;i<E;++i) c[i]=a[g[E-1-i]];
	for(int i=0;i<L;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(H-1));
	FFT(c,H,1); FFT(b,H,1);
	for(int i=0;i<L;++i) a[i]=c[i]*b[i];
	FFT(a,H,-1);
	for(int i=0;i<P;++i) a[i]=a[i]+a[i+P-1];
	for(int i=1;i<P;++i) Ans[g[i]]+=a[i-1].r;
	for(int i=0;i<P;++i) printf("%.3lf ",Ans[i]); printf("\n");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d",&P)!=EOF) solve();
	return 0;
}

本文标题:【HDU5958】New Signal Decomposition

文章作者:chty

发布时间:2019年02月18日 - 11时30分

最后更新:2019年02月18日 - 12时04分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,