2015 HN Training 7.7 A

2024-04-16 13:18

本文主要是介绍2015 HN Training 7.7 A，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

时间限制 : 3000 MS 空间限制 :64MB

样例输入

3 2 2
1 2 3
0 1

样例输出

1 4 8

题解

NTT板题，只需用卷积的套路稍微转化一下……
每出现一个元素 $c$ ，便对多项式 $g_c++$ 即可。对 $f$ 进行 $k$ 次变换，即对 $f$ 乘上 $g$ 的 $k$ 次方，用快速幂解决即可。需要注意的是，每次多项式乘法时都需对多项式进行正逆变换，消除次数不小于n的项，避免多项式最高次超出NTT的限制范围。时间复杂度为 $O(nlognlogk)$

代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const ll mod=950009857;
const ll G=7;
ll a,n,m,k,N=1,f[maxn<<2],g[maxn<<2],ntt[maxn<<2];
inline ll input()
{char t=getchar();ll x=0,flag=0;while(t<48||t>57){if(t=='-') flag=1;t=getchar();}for(;t>=48&&t<=57;t=getchar()) x=x*10+t-48;return flag?-x:x; 
}
ll ksm(ll a,ll b)
{ll temp=1;while(b){if(b&1) temp=temp*a%mod;b>>=1,a=a*a%mod;}return temp;
}
void NTT(ll A[],ll n,ll ty)
{ll t0,t1;for(ll i=0,j=0;i<n;i++){if(i<j) swap(A[i],A[j]);for(ll k=n>>1;(j^=k)<k;k>>=1);}ntt[0]=1;for(ll m=1;m<n;m<<=1){t0=ksm(G,mod-1+ty*(mod-1)/(m<<1));for(ll i=1;i<m;i++) ntt[i]=ntt[i-1]*t0%mod;for(ll k=0;k<n;k+=(m<<1))for(ll i=k;i<k+m;i++){t0=A[i],t1=A[i+m]*ntt[i-k]%mod;A[i]=t0+t1,A[i]-=A[i]>=mod?mod:0;A[i+m]=t0-t1,A[i+m]+=A[i+m]<0?mod:0;}}if(ty==1) return;t0=ksm(n,mod-2);for(ll i=0;i<n;i++) A[i]=A[i]*t0%mod;
}
void poly_ksm(ll b)
{while(b){NTT(g,N,1);if(b&1){NTT(f,N,1);for(ll i=0;i<N;i++) f[i]=f[i]*g[i]%mod;NTT(f,N,-1);for(ll i=n;i<N;i++) f[i]=0;}b>>=1;for(ll i=0;i<N;i++) g[i]=g[i]*g[i]%mod;NTT(g,N,-1);for(ll i=n;i<N;i++) g[i]=0;}
}
int main()
{n=input(),m=input(),k=input();for(ll i=0;i<n;i++) f[i]=input()%mod;for(ll i=0;i<m;i++) a=input(),g[a]++;while(N<=n+n) N<<=1;poly_ksm(k);for(ll i=0;i<n;i++) printf("%lld ",f[i]);return 0;
}