[xsy1140]求值

$\newcommand{ali}[1]{\begin{align*}#1\end{align*}}$题意：给定$n,b,c,d,e,a_{0\cdots n-1}$，令$x_k=bc^{4k}+dc^{2k}+e$，$f(x)=\sum\limits_{i=0}^{n-1}a_ix^i$，求$f(x_{0\cdots n-1})$

如果单纯看推公式的话，这题没什么思维含量，但对各种卷积的处理还是需要一定的思考的

1.$c=0$，此时$x_0=b+d+e$，$x_{1\cdots n-1}=e$，直接算即可

2.$b=0$，我们来推导一番

$\ali{f(x_k)&=\sum\limits_{i=0}^{n-1}a_i(dc^{2k}+e)^i\\&=\sum\limits_{i=0}^{n-1}a_i\sum\limits_{j=0}^i\binom ijd^jc^{2kj}e^{i-j}\\&=\sum\limits_{j=0}^{n-1}\dfrac{d^jc^{2kj}}{j!}\sum\limits_{i=j}^{n-1}\dfrac{a_ii!e^{i-j}}{(i-j)!}}$

令$p_j=\sum\limits_{i=j}^{n-1}\frac{a_ii!e^{i-j}}{(i-j)!}$，这是$a_ii!(i=n-1\cdots0)$卷$\frac{e^i}{i!}(i=0\cdots n-1)$的$n-1-j$项

$\ali{\sum\limits_{j=0}^{n-1}\dfrac{d^jc^{2kj}p_j}{j!}&=c^{k^2}\sum\limits_{j=0}^{n-1}\dfrac{c^{-(k-j)^2}c^{j^2}d^jp_j}{j!}\\&=c^{k^2}\left(\sum\limits_{j=0}^k\dfrac{c^{-(k-j)^2}c^{j^2}d^jp_j}{j!}+\sum\limits_{j=k+1}^{n-1}\dfrac{c^{-(j-k)^2}c^{j^2}d^jp_j}{j!}\right)}$

第一个sigma是$c^{-i^2}(i=0\cdots n-1)$卷$\frac{c^{i^2}d^ip_i}{i!}(i=0\cdots n-1)$的$k$项，第二个sigma是$\frac{c^{i^2}d^ip_i}{i!}(i=n-1\cdots1)$卷$c^{-i^2}(i=1\cdots n-1)$的$n-2-k$项

3.一般情况

我们先配方，$bc^{4k}+dc^{2k}+e=b\left(c^{2k}+\frac d{2b}\right)^2+e-\frac{d^2}{4b}$，重新定义$d=\frac d{2b},e=e-\frac{d^2}{4b}$，于是$x_k=b(c^{2k}+d)^2+e$

$\ali{f(x_k)&=\sum\limits_{i=0}^{n-1}a_i\left[b\left(c^{2k}+d\right)^2+e\right]^2\\&=\sum\limits_{i=0}^{n-1}a_i\sum\limits_{j=i}^{n-1}\binom ijb^j\left(c^{2k}+d\right)^{2j}e^{i-j}\\&=\sum\limits_{j=0}^{n-1}\dfrac{b^j\left(c^{2k}+d\right)^{2j}p_j}{j!}\\&=\sum\limits_{j=0}^{n-1}\dfrac{b^jp_j}{j!}\sum\limits_{l=0}^{2j}\binom{2j}lc^{2kl}d^{2j-l}\\&=\sum\limits_{l=0}^{2n-2}\dfrac{c^{2kl}}{l!}\sum\limits_{j=\left\lceil\frac l2\right\rceil}^{n-1}\dfrac{(2j)!d^{2j-l}b^jp_j}{j!(2j-l)!}}$

令$q_l=\sum\limits_{j=\left\lceil\frac l2\right\rceil}^{n-1}\frac{(2j)!d^{2j-l}b^jp_j}{j!(2j-l)!}$，下面分别对$l$为奇数和偶数的情况分开讨论，因为式子中偏移$-l$的项含$2j$，所以推式子的时候要适当换元$t=2j$

$l$为奇数，是$\frac{(2i)!b^ip_i}{i!}(i=n-1\cdots1)$卷$\frac{d^{2i-1}}{(2i-1)!}(i=1\cdots n-1)$的$n-1-\frac{l+1}2$项

$l$为偶数，是$\frac{(2i)!b^ip_i}{i!}(i=n-1\cdots0)$卷$\frac{d^{2i}}{(2i)!}(i=0\cdots n-1)$的$n-1-\frac l2$项

$\ali{\sum\limits_{l=0}^{2n-2}\dfrac{c^{2kl}q_l}{l!}&=c^{k^2}\sum\limits_{l=0}^{2n-2}\dfrac{c^{-(k-l)^2}c^{l^2}q_l}{l!}\\&=c^{k^2}\left(\sum\limits_{l=0}^k\dfrac{c^{-(k-l)^2}c^{l^2}q_l}{l!}+\sum\limits_{l=k+1}^{2n-2}\dfrac{c^{-(l-k)^2}c^{l^2}q_l}{l!}\right)}$

第一个sigma是$c^{-i^2}(i=0\cdots n-1)$卷$\frac{c^{i^2}q_i}{i!}(i=0\cdots n-1)$的$k$项，第二个sigma是$\frac{c^{i^2}q_i}{i!}(i=2n-2\cdots1)$卷$c^{-i^2}(i=1\cdots2n-2)$的$2n-3-k$项

然后就做完了，感觉略毒...

#include<stdio.h>
#include<string.h>
#include<math.h>
typedef long long ll;
const int mod=1000003,maxn=524288;
typedef double du;
int mul(int a,int b){return a*(ll)b%mod;}
int ad(int a,int b){return(a+b)%mod;}
int de(int a,int b){return(a-b)%mod;}
int pow(int a,ll b){
	int s=1;
	while(b){
		if(b&1)s=mul(s,a);
		a=mul(a,a);
		b>>=1;
	}
	return s;
}
struct complex{
	du x,y;
	complex(du a=0,du b=0){x=a;y=b;}
};
complex operator+(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void swap(complex&a,complex&b){
	complex c=a;
	a=b;
	b=c;
}
int rev[maxn],N;
complex w[19][maxn];
void pre(int n){
	int i,j,k;
	for(N=1,k=0;N<n;N<<=1)k++;
	for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
	k=0;
	for(i=2;i<=N;i<<=1){
		for(j=0;j<i;j++)w[k][j]=complex(cos(j*M_PI/(i/2)),sin(j*M_PI/(i/2)));
		k++;
	}
}
void fft(complex*a,int on){
	int i,j,k,f;
	complex t;
	for(i=0;i<N;i++){
		if(i<rev[i])swap(a[i],a[rev[i]]);
	}
	f=0;
	for(i=2;i<=N;i<<=1){
		for(j=0;j<N;j+=i){
			for(k=0;k<i>>1;k++){
				t=w[f][k];
				if(on==-1)t.y=-t.y;
				t=t*a[i/2+j+k];
				a[i/2+j+k]=a[j+k]-t;
				a[j+k]=a[j+k]+t;
			}
		}
		f++;
	}
	if(on==-1){
		for(i=0;i<N;i++)a[i].x/=N;
	}
}
complex A[maxn],B[maxn],C[maxn],D[maxn];
void conv(int*a,int*b,int*c){
	int i;
	complex t;
	for(i=0;i<N;i++){
		A[i]=a[i]>>10;
		B[i]=a[i]&1023;
		C[i]=b[i]>>10;
		D[i]=b[i]&1023;
	}
	fft(A,1);
	fft(B,1);
	fft(C,1);
	fft(D,1);
	for(i=0;i<N;i++){
		t=A[i]*D[i]+B[i]*C[i];
		A[i]=A[i]*C[i];
		C[i]=B[i]*D[i];
		B[i]=t;
	}
	fft(A,-1);
	fft(B,-1);
	fft(C,-1);
	for(i=0;i<N;i++)c[i]=((llround(A[i].x)%mod<<20)+(llround(B[i].x)%mod<<10)+llround(C[i].x)%mod)%mod;
}
int a[maxn],t1[maxn],t2[maxn],t3[maxn],fac[maxn],rfac[maxn],p[maxn],s[maxn],f1[maxn],f2[maxn],n,b,c,d,e;
namespace c0{
	int get(int x){
		int s,t,i;
		s=0;
		t=1;
		for(i=0;i<n;i++){
			s=ad(s,mul(t,a[i]));
			t=mul(t,x);
		}
		return ad(s,mod);
	}
	void solve(){
		int i,s1,s2;
		s1=get(b+d+e);
		s2=get(e);
		printf("%d\n",s1);
		for(i=1;i<n;i++)printf("%d\n",s2);
	}
}
namespace b0{
	void solve(){
		int i,t,u,v,w;
		t=1;
		for(i=0;i<n;i++){
			t1[n-1-i]=mul(a[i],fac[i]);
			t2[i]=mul(t,rfac[i]);
			t=mul(t,e);
		}
		conv(t1,t2,t3);
		for(i=0;i<n;i++)p[i]=t3[n-1-i];
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		t=pow(c,mod-2);
		u=1;
		v=1;
		w=1;
		for(i=0;i<n;i++){
			t1[i]=u;
			t2[i]=mul(mul(v,w),mul(p[i],rfac[i]));
			u=mul(u,pow(t,i*2+1));
			v=mul(v,pow(c,i*2+1));
			w=mul(w,d);
		}
		conv(t1,t2,t3);
		for(i=0;i<n;i++)f1[i]=t3[i];
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		u=t;
		v=c;
		w=d;
		for(i=1;i<n;i++){
			t1[n-1-i]=mul(mul(v,w),mul(p[i],rfac[i]));
			t2[i-1]=u;
			u=mul(u,pow(t,i*2+1));
			v=mul(v,pow(c,i*2+1));
			w=mul(w,d);
		}
		conv(t1,t2,t3);
		for(i=0;i<n;i++)f2[i]=t3[n-2-i];
		u=1;
		for(i=0;i<n;i++){
			s[i]=mul(u,ad(f1[i],f2[i]));
			u=mul(u,pow(c,i*2+1));
		}
		for(i=0;i<n;i++)printf("%d\n",ad(s[i],mod));
	}
}
namespace def{
	int q[maxn];
	void solve(){
		int i,t,u,v;
		u=mul(d,pow(2*b%mod,mod-2));
		v=de(e,mul(mul(d,d),pow(4*b%mod,mod-2)));
		d=u;
		e=v;
		t=1;
		for(i=0;i<n;i++){
			t1[n-1-i]=mul(a[i],fac[i]);
			t2[i]=mul(t,rfac[i]);
			t=mul(t,e);
		}
		conv(t1,t2,t3);
		for(i=0;i<n;i++)p[i]=t3[n-1-i];
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		t=1;
		u=d;
		for(i=1;i<n;i++){
			t=mul(t,b);
			t1[n-1-i]=mul(mul(fac[i*2],mul(t,p[i])),rfac[i]);
			t2[i-1]=mul(u,rfac[2*i-1]);
			u=mul(u,mul(d,d));
		}
		conv(t1,t2,t3);
		for(i=1;i<=2*n-2;i+=2)q[i]=t3[n-1-(i+1)/2];
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		t=1;
		u=1;
		for(i=0;i<n;i++){
			t1[n-1-i]=mul(mul(fac[i*2],mul(t,p[i])),rfac[i]);
			t2[i]=mul(u,rfac[2*i]);
			t=mul(t,b);
			u=mul(u,mul(d,d));
		}
		conv(t1,t2,t3);
		for(i=0;i<=2*n-2;i+=2)q[i]=t3[n-1-i/2];
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		t=pow(c,mod-2);
		u=1;
		v=1;
		for(i=0;i<n;i++){
			t1[i]=u;
			t2[i]=mul(mul(v,q[i]),rfac[i]);
			u=mul(u,pow(t,i*2+1));
			v=mul(v,pow(c,i*2+1));
		}
		conv(t1,t2,t3);
		for(i=0;i<n;i++)f1[i]=t3[i];
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		u=t;
		v=c;
		for(i=1;i<=2*n-2;i++){
			t1[2*n-2-i]=mul(mul(v,q[i]),rfac[i]);
			t2[i-1]=u;
			u=mul(u,pow(t,i*2+1));
			v=mul(v,pow(c,i*2+1));
		}
		pre(n<<2);
		conv(t1,t2,t3);
		for(i=0;i<n;i++)f2[i]=t3[2*n-3-i];
		u=1;
		for(i=0;i<n;i++){
			s[i]=mul(u,ad(f1[i],f2[i]));
			u=mul(u,pow(c,2*i+1));
		}
		for(i=0;i<n;i++)printf("%d\n",ad(s[i],mod));
	}
}
int main(){
	int i;
	scanf("%d%d%d%d%d",&n,&b,&c,&d,&e);
	for(i=0;i<n;i++)scanf("%d",a+i);
	pre(n<<1);
	fac[0]=1;
	for(i=1;i<N;i++)fac[i]=mul(fac[i-1],i);
	rfac[N-1]=pow(fac[N-1],mod-2);
	for(i=N-1;i>0;i--)rfac[i-1]=mul(rfac[i],i);
	if(c==0)
		c0::solve();
	else if(b==0)
		b0::solve();
	else
		def::solve();
}

巴特西

[xsy1140]求值

最新文章

热门文章