如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
首先，有一个显而易见的结论，我们要求的答案是原数组的乘积减去 $k$ 次操作后数组的乘积的期望。
我们设每个数被选中的次数为 $b_i$，则我们要求的是 $E(\prod\limits_{i=1}^n(a_i-b_i))$，如果枚举所有种类的 $b_i$，即 \(\frac{1}{n^k}k!\prod_{i=1}^n\frac{(a_i-b_i)}{b_i!}\) 我们写出后面这个东西的生成函数：
\[\begin{aligned} F_k(x)=&\sum\limits_{i=0}^\infin\frac{(a_k-i)x^i}{i!}\\ =&\sum\limits_{i=0}^\infin\frac{a_kx^i}{i!}-\sum\limits_{i=0}^\infin\frac{ix^i}{i!}\\ =&a_k\sum\limits_{i=0}^\infin\frac{x^i}{i!}-x\sum\limits_{i=0}^\infin\frac{x^i}{i!}\\ =&(a_k-x)e^x\\ \end{aligned}\]我们要求的就是 $[x^k]\prod\limits_{i=1}^nF_i(x)=[x^k] (e^{nx}\prod\limits_{i=1}^n(a_i-x))=[x^k] ((\sum\limits_{i=0}^\infin\frac{n^ix^i}{i!})\prod\limits_{i=1}^n(a_i-x))$。
$\prod\limits_{i=1}^n(a_i-x)$ 是一个 $n$ 次多项式，本题中可以暴力计算，所以我们将其写成 $\sum\limits_{i=0}^nf_ix^i$ 的形式。
答案即为
\[\frac{1}{n^k}k!\sum\limits_{i=0}^nf_i\frac{n^{k-i}}{(k-i)!}=\sum\limits_{i=0}^nf_in^{-i}k^{\underline{i}}\]最后记得用 $\prod\limits_{i=1}^na_i$ 减去即可。
#include<cstdio>
#include<algorithm>
int const mod=1e9+7;
int n,k,prod=1,a[5010],b[5010];
int pow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
int main(){
scanf("%d%d",&n,&k);
a[0]=1;
for(int x,i=1;i<=n;i++){
scanf("%d",&x);
prod=1ll*prod*x%mod;
for(int j=0;j<i;j++)b[j]=1ll*a[j]*x%mod;
for(int j=0;j<i;j++)b[j+1]=(b[j+1]+(mod-1ll)*a[j])%mod;
std::swap(a,b);
}
for(int i=0,fac=1;i<=n;fac=1ll*fac*(k-i)%mod,i++) prod=(prod+(mod-1ll)*a[i]%mod*pow(pow(n,mod-2),i)%mod*fac)%mod;
printf("%d\n",prod);
return 0;
}