题目大意

有 n 个数 $a_1,a_2…a_n$，你要进行 $k$次操作，每次随机选择一个数 $a_x$，使得 $res+=\prod_{i \neq x} a_i$，求最后 $res$的期望，对 1e9+7 取模。

题目分析

由于 $(a_x-1)\prod_{i \neq x} a_i=(a_x \prod_{i \neq x} a_i)-\prod_{i \neq x} a_i$
所以初始的 $n$个数的累乘-完成操作后 $n$个数的累乘就是 $res$啦~
假设 $d_i$为第 i 个数被选择的次数，那么完成操作后的期望为（A 为所有 $a_i$构成的集合)：
$$\prod a_id_i =\prod_{S \subset A} (-1)^{|S|} \prod_{i \in S} d_i \prod_{i \not\in S}a_i$$
对于 $\prod_{i \not\in S}a_i$，我们可以用一个类似背包的方法 $O(n^2)$求一下：

    for(int i=1;i<=n;++i) {
        cin>>x;
        for(int j=i;j>=1;--j) f[j]=(f[j]+f[j-1]*x)%mod;//x 被选的情况
    }

而 $\prod_{i \in S} d_i $呢？可以视作有 n 个数，都是 0，进行 k 次操作，每次操作为把某个数加 1，求期望这些数最后的累乘。
先考虑 $n=2$的情况，显然:$$ans=\sum_{i=0}^k C_k^i i \times (k-i)$$
将组合数写成通项公式后化简得到:$$ans=k(k-1)2^{k-2}$$
这样似乎很难推到更大的 n 的情况，不过引用某 Cai 大佬的话：

可以换一个角度看那个式子的含义，可以看成是有 n 个人要依次被双线程处决，我们要选一些人枪毙，选一些人砍死。第一个式子就是先枚举多少人被枪毙，多少人被砍死，再看被枪毙的人里谁先死，被砍死的人里谁先死（方案数 $i \times (k-i)$种嘛，枪毙的人里第一个死的有 $i$中选法，砍死的人里有 $k-i$种。）
所以第二个式子可以看作是先枚举谁先被枪毙 ($k$种)，再枚举谁第一个被砍死 ($k-1$种)，剩下的人游离于刀枪乱棍之中，无需在乎他们怎么死，只要方案数是对的就可以。

额，这个例子很凶残，但是还是很形象的。（Cai 大佬在跟我解释的时候还画图了的，没图可能有点难理解）
这样，我们可以发明更多处决方式（大雾），推广到 $n$更大的情况。同样，我们还可以通过这种思想，知道假如我们只想求前 i 个数的累乘期望，就是 $$k(k-1)…(k-i+1)n^{k-i}$$
自此，本题以 $O(n^2)$的复杂度完美解决，撒花~

代码

为什么用 cin 和 cout 呢？…… 因为我也不知道为什么用 scanf 就 WA 了呀。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod=1000000007;
LL n,k,f[5005];
LL ksm(LL x,LL y) {
    LL re=1;
    for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod;
    return re;
}
int main()
{
    LL x,k1,k2=1,niy,fh;f[0]=1;
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>x;
        for(int j=i;j>=1;--j) f[j]=(f[j]+f[j-1]*x)%mod;
    }
    niy=ksm(n,mod-2),fh=1;
    for(int i=n;i>=0;--i) {
        k1=(k1+fh*f[i]%mod*k2%mod)%mod;
        k2=k2*(k-n+i)%mod*niy%mod,fh=-fh;
    }
    cout<<((f[n]-k1+mod)%mod)<<endl;
    return 0;
}