arc106d 题解

ARC106D

思路

左边到右边不好，改为任意一个到另一个。

$an{s}_x=\frac{1}{2}({\sum }_i^n{\sum }_j^n(a_i+a_j{)}^x-{\sum }_i^n(2\times a_i{)}^x)$

拆开 $k$ 次方。

$(a_i+a_j{)}^x={\sum }_{k=0}^x(\left(\genfrac{}{}{0ex}{}{x}{k}\right)\times {a_i}^k\times {a_j}^{x-k})$

$an{s}_x=\frac{1}{2}({\sum }_{k=0}^x({\sum }_i^n{a_i}^k\times {\sum }_j^n{a_j}^{x-k})-{\sum }_i^n(2\times a_i{)}^x)$

预处理 $su{m}_k={\sum }_i{a_i}^k$。

$an{s}_x=\frac{1}{2}({\sum }_{k=0}^x(su{m}_k\times su{m}_{x-k})-2^x\times su{m}_x)$

复杂度 $O(nk+k^2)$。

code

int n,x,a[maxn];
inline int ksm(int a,int b=mod-2,int p=mod){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
int ans,ni;
int fac[maxn],inv[maxn];
int C(int m,int n){return fac[m]*inv[n]%mod*inv[m-n]%mod;}
int sum[maxm],mul[maxn];
void work(){
	n=read();x=read();
	for(int i=1;i<=n;i++)a[i]=read(),mul[i]=1;
	for(int k=0;k<=x;k++){
		for(int i=1;i<=n;i++)sum[k]+=mul[i],sum[k]%=mod;
		for(int i=1;i<=n;i++)mul[i]=mul[i]*a[i]%mod;
//		cout<<sum[k]<<" ";
	}
//	cout<<"\n";
	fac[0]=1;for(int i=1;i<=x;i++)fac[i]=fac[i-1]*i%mod;
	inv[x]=ksm(fac[x]);
	for(int i=x-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
	ni=ksm(2);
	for(int i=1;i<=x;i++){
		ans=0;
		for(int k=0;k<=i;k++)ans+=C(i,k)*sum[k]%mod*sum[i-k]%mod,ans%=mod;
		ans+=mod-ksm(2,i)*sum[i]%mod,ans%=mod;
		ans*=ni,ans%=mod;
		printf("%lld\n",ans);
	}
}