题目链接
题意简述
你有长为(n)的序列和(Q)个询问，每次询问一个(k)，求用(k)个数组成的不同方案的乘积的和。
sol
显然要预处理一波。
考虑分治，左右两边都求出来后，怎么合并。
设(A[i])为整体用(i)个数的乘积和，(B[i])为左边用(i)个数的乘积和，(C[i])为右边用(i)个数的乘积和。
则很显然有(A[i]=sum_{j=0}^i B[j]C[i-j])
这是一个卷积然后NTT就好了，然而怎么模数是1e5+3，那就双模数NTT吧，虽然常数巨大，FFT也可以，写的好的话常数优秀5~6倍。总复杂度(O(nlog^2n))。
疯狂压行ing~
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in(){int k=0;char ch=gt;while(ch<'-')ch=gt;while(ch>'-')k=k*10+ch-'0',ch=gt;return k;}
const int N=3e5+5,g=3,p[]={998244353,1004535809},inv[]={669690699,332747959};const ll MOD=1ll*p[0]*p[1];
int rev[N],v1[N],v2[N],v3[N],v4[N];ll f[50][N];
inline int MO(const int &a,int now){return a>=p[now]?a-p[now]:a;}
inline int ksm(int a,int k,int now){int r=1;while(k){if(k&1)r=1ll*r*a%p[now];a=1ll*a*a%p[now],k>>=1;}return r;}
inline ll mul(ll a,ll k ){ll r=0;while(k){if(k&1)r=(r + a)% MOD ;a=(a + a)% MOD ,k>>=1;}return r;}
void get_rev(int len,int qwq){rev[0]=0;for(int i=1;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<qwq-1);}
void ntt(int *a,int len,int opt,int now)
{
#define YL p[now]
for(int i=0;i<len;++i)if(i<rev[i])std::swap(a[i],a[rev[i]]);
for(int st=2,m=1;st<=len;st<<=1,m<<=1)
{
int wn=ksm(g,opt==1?(YL-1)/st:YL-1-(YL-1)/st,now);
for(int *pp=a;pp!=a+len;pp+=st)
for(int k=0,wnk=1;k<m;++k,wnk=1ll*wnk*wn%YL)
{
int t=1ll*wnk*pp[k+m]%YL;
pp[k+m]=MO(pp[k]-t+YL,now);
pp[k]=MO(pp[k]+t,now);
}
}
if(opt==1)return;int inv=ksm(len,YL-2,now);
for(int i=0;i<len;++i)a[i]=1ll*a[i]*inv%YL;
#undef YL
}
const int YL=1e5+3;
int a[N];
void get_mul(int *a,int *b,int len,int now)
{
ntt(a,len, 1,now);ntt(b,len, 1,now);
for(int i=0;i<len;++i)a[i]=1ll*a[i]*b[i]%p[now];
ntt(a,len,-1,now);
}
void cdq_fft(int l,int r,int x)
{
for(int i=0;i<=r-l+1;++i)f[x][i]=0;
if(l==r){f[x][0]=1,f[x][1]=a[l];return;}
int mid=l+r>>1;cdq_fft(l,mid,x+1);
for(int i=0;i<=r-l+1;++i)f[x][i]=f[x+1][i];cdq_fft(mid+1,r,x+1);
int m=r-l+1,qwq=0,len=1;
while(len<=m)len<<=1,++qwq;get_rev(len,qwq);
for(int i=r-mid+1;i<len;++i)f[x+1][i]=0;
for(int i=mid-l+2;i<len;++i)f[ x ][i]=0;
for(int i=0;i<len;++i)v1[i]=v2[i]=f[x][i],v3[i]=v4[i]=f[x+1][i];
get_mul(v1,v3,len,0);get_mul(v2,v4,len,1);
for(int i=0;i<=m;++i)
{
f[x][i]=mul(1ll*v1[i]*p[1]%MOD,inv[1]);
ll tttt=mul(1ll*v2[i]*p[0]%MOD,inv[0]);
f[x][i]=(f[x][i]+tttt)%MOD;
f[x][i]=(f[x][i]+YL)%YL;
}
}
int main()
{
int n=in(),q=in();for(int i=1;i<=n;++i)a[i]=in()%YL;
cdq_fft(1,n,0);while(q--)printf("%lld
",f[0][in()]);
return 0;
}