Description：

有 $n$ 个数 $a_1,a_2\dots a_n$ ， $k$ 次操作，每次随机选择一个数 $x$ ，使得 $res+=\prod_{i \neq x}a_i$ ，求最后 $res$ 值的期望。

$1\leqslant n\leqslant 5000$

Solution：

首先有一个神仙结论：设第 $i$ 个数被减了 $b_i$ 次，那么最后的值为： $$ \prod_{i=1}^na_i-\prod_{i=1}^n(a_i-b_i) $$ 那么我们显然可以只计算后面那一部分的期望，式子是： $$ \begin{align} &\frac{\begin{align}\sum_{b_1+b_2+\cdots +b_n=k}\binom{k}{b_1,b_2,\dots,b_n}\prod_{i=1}^n(a_i-b_i)\end{align}}{n^k}\\ =&\frac{k!}{n^k}\sum_{b_1+b_2+\dots+b_n=k}\prod_{i=1}^n\frac{a_i-b_i}{b_i!} \end{align} $$ 不难看出是一个卷积，设： $$ F_i(x)=\sum_{n\geqslant 0}\frac{a_i-n}{n!}x^n,F(x)=\prod_{i=1}^nF_i(x) $$ 那么： $$ ans=\frac{k!}{n^k}[x^k]F(x) $$ 于是我们的问题变成了求 $F$ ，观察一下我们又可以发现一个神仙结论： $$ (a_i-x)\sum_{n\geqslant 0}\frac{x^n}{n!}=\sum_{n\geqslant 0}\frac{a_i}{n!}x^n-\sum_{n\geqslant 0}\frac{jx^n}{j!}\sum_{n\geqslant 0}\frac{a_i-n}{n!}x^n $$ 那么 $F(x)=\prod(a_i-x)e^{nx}$ 。

于是前面暴力展开 $O(n^2)$ ，后面用泰勒展开，然后暴力卷积一下即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 5010

int a[MAXN];

int v[MAXN][MAXN];

int e[MAXN];

#define P 1000000007

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	v[0][0] = 1;

	for(int k = 1;k <= n;++k)

	{

		for(int i = 0;i <= n;++i)

		{

			v[k][i] = (v[k][i] + 1ll * a[k] * v[k - 1][i] % P) % P;

			v[k][i] = (v[k][i] + 1ll * (P - 1) * v[k - 1][i - 1] % P) % P;

		}

	}

	int ans = 0;

	for(int i = 0;i <= n;++i)

	{

		int mul = 1;

		for(int j = k - i + 1;j <= k;++j)mul = 1ll * mul * j % P;

		ans = (ans + 1ll * v[n][i] * mul % P * power(power(n,i),P - 2) % P) % P;

	}

	cout << (v[n][0] - ans + P) % P;

	return 0;

}