如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
考虑写出花和巧克力的生成函数：
\[F(x)=(\sum x^{p_i})^n=\sum\limits_{i=0}^{\infin} F_ix^i\\ G(x)=\sum\limits_{j=0}^{\infin}(\sum x^{c_i})^j=\sum\limits_{i=0}^{\infin}G_ix^i\]我们求的就是 $\sum\limits_{i=0}^{\infin}F_iG_i$。
$G$ 其实是完全背包，由于 $c_i$ 很小，考虑写成递推式。
\[G_n=\sum\limits_{i=1}^mG_{n-i}k_i\]其中 $k_i=\sum_j[c_j=i]$。
根据常系数齐次线性递推的结论，有
\[P(x)=x^m-\sum\limits_{i=0}^{m}k_{m-i}x^i\\ G_i=[x^{m-1}](x^{m+i-1}\bmod P(x))\]又有
\[F_i=[x^i](\sum_j x^{p_j})^n=[x^{m+i-1}](x^{m-1}(\sum_j x^{p_j})^n)\]于是答案为
\[[x^{m-1}](x^{m-1}(\sum_j x^{p_j})^n\bmod P(x))\]#include<cstdio>
#include<algorithm>
int const mod=1e9+7;
int an,bn,a[20],b[510],m;
void mul(int const *a,int const *b,int *ans){
static int c[510];
for(int i=0;i<=2*m-2;i++) c[i]=0;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
c[i+j]=(c[i+j]+1ll*a[i]*b[j])%mod;
for(int i=2*m-2;i>=m;i--)
for(int j=0;j<=m;j++)
c[i-(m-j)]=(c[i-(m-j)]-1ll*::b[j]*c[i]%mod+mod)%mod;
for(int i=0;i<m;i++) ans[i]=c[i];
}
long long n;
int main(){
scanf("%d%d%lld",&an,&bn,&n);
for(int i=1;i<=an;i++) scanf("%d",a+i);
for(int i=1,x;i<=bn;i++) scanf("%d",&x),++b[x],m=std::max(m,x);
std::reverse(b,b+m+1),b[m]=1;
for(int i=0;i<m;i++) b[i]=(mod-b[i])%mod;
static int o[510],t[510];
for(int i=1;i<=an;i++){
static int k[510],res[510];
for(int i=0;i<m;i++) res[i]=k[i]=0;
if(m!=1) k[1]=1;
else k[0]=mod-b[0];
res[0]=1;
while(a[i]){
if(a[i]&1) mul(res,k,res);
a[i]>>=1,mul(k,k,k);
}
for(int i=0;i<m;i++) o[i]=(o[i]+res[i])%mod;
}
t[0]=1;
while(n){
if(n&1) mul(t,o,t);
n>>=1,mul(o,o,o);
}
for(int i=0;i<m;i++) o[i]=0;
o[m-1]=1;
mul(t,o,t);
printf("%d\n",t[m-1]);
return 0;
}