CF891E Lust

传送门

题目大意

你有 \(n\) 个数 \(a_1,a_2...a_n\)

要进行 \(k\) 次操作

每次随机选择一个数 \(x\)，使得答案加上 \(\prod_{i \neq x}a_i\) ，并将 \(a_x\) 减去 \(1\)

求最后答案的期望，对 \(1e9+7\) 取模

Sol

设 \(b_i\) 表示 \(i\) 选择了多少次

把对 \(a_x\) 的一次操作的贡献看成是

\[\prod a_i−\prod a′_i
\]

其中 \(a′_i\) 表示将 \(a_x\) 减去 \(1\) 后的数组。

连续操作后，剩下的项就只剩下

\[\prod a_i−\prod(a_i−b_i)
\]

考虑计算 \(\prod(a_i−b_i)\) 的期望

考虑生成函数

答案就是

\[\prod_{i=1}^{n}(\sum_{j=0}^{\infty}\frac{a_i-j}{j!}x^j)[x^k]
\]

\([x^k]\) 表示 \(x^k\) 的系数，最后乘上 \(k!\) 和 \(\frac{1}{n^k}\)

那一坨东西化简一下就是

\[e^{nx}\prod_{i=1}^{n}(a_i-x)
\]

\(e^{nx}\) 直接泰勒展开求就好了，后面的直接分治NTT暴力卷起来就好了

最后把两个多项式再卷一下

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod(1e9 + 7);

const int maxn(5005);

inline void Inc(int &x, int y) {

	if ((x += y) >= mod) x -= mod;

}

inline int Pow(ll x, int y) {

	register ll ret = 1;

	for (; y; y >>= 1, x = x * x % mod)

		if (y & 1) ret = ret * x % mod;

	return ret;

}

int f[maxn], n, k, ans;

int main() {

	register int i, j, a, fac, cur;

	scanf("%d%d", &n, &k), f[0] = 1;

	for (i = 1; i <= n; ++i) {

		scanf("%d", &a);

		for (j = i; j; --j) f[j] = 1LL * f[j] * a % mod, Inc(f[j], mod - f[j - 1]);

		f[0] = 1LL * f[0] * a % mod;

	}

	a = Pow(n, 1LL * k * (mod - 2) % (mod - 1)), cur = Pow(n, k - min(n, k));

	for (fac = 1, i = k - min(n, k) + 1; i <= k; ++i) fac = 1LL * fac * i % mod;

	for (i = min(n, k); ~i; --i) {

		Inc(ans, 1LL * f[i] * fac % mod * cur % mod);

		cur = 1LL * cur * n % mod, fac = 1LL * fac * Pow(k - i + 1, mod - 2) % mod;

	}

	ans = 1LL * ans * a % mod, ans = (f[0] - ans + mod) % mod;

	printf("%d\n", ans);

	return 0;

}