VEXOBEN
Vexoben
Mar 8, 2019
It takes 4 minutes to read this article.

题目链接:CF891E Lust

又被神仙题D没了

(刷新以获取数学公式)

题意

给定个数,第个数为.进行次操作,每次随机选择一个数,将答案加上,并,求最后答案的期望.

数据范围: ,模输出

加强:

题解

选到数对答案的贡献是,这不好计算.但是我们惊奇地发现,这个式子等于:

其中后的数组.

显然可以发现操作顺序对答案没有影响.

那么我们枚举每个数被选到多少次.设第个数被选到的次数为.

可以发现第一个数对答案的贡献是

最后可以发现游戏的答案就是

因此我们的答案就是以下式子:

稍微处理一下就是:

这步之后用生成函数进行优化,设

那么它的生成函数就是:

下面不加证明地给出最近学习生成函数得到的几个式子:

根据式,最终可以将式子化简为:

其中 表示 次项系数.

暴力(或者分治NTT)算出来,脑补一下泰勒展开就可以计算了.

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5005;
const int mod = 1e9 + 7;

int n, k;
int a[N];
LL f[N], g[N], s[N];

LL Qpow(LL x, int p) {
	LL ans = 1;
	for (; p; p >>= 1) {
		if (p & 1) ans = ans * x % mod;
		x = x * x % mod;
	}
	return ans;
}

LL Inv(LL x) {
	return Qpow(x, mod - 2);
}

void upd(LL &x, LL y) {
	x = (x + y >= mod) ? (x + y - mod) : (x + y);
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	s[0] = 1; s[1] = k;
	for (int i = 2; i <= n; ++i) {
		s[i] = s[i - 1] * (k - i + 1) % mod;
	}
	LL ans = 1;
	for (int i = 1; i <= n; ++i) {
		ans = ans * a[i] % mod;
	}
	f[0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = n; j >= 0; --j) {
			g[j] = 0;
			upd(g[j], f[j] * a[i] % mod);
			if (j) upd(g[j], mod - f[j - 1]);
		}
		for (int j = 0; j <= n; ++j) {
			f[j] = g[j];
		}
	}
	LL ans2 = 0;
	for (int i = 0; i <= n && i <= k; ++i) {
		LL tmp = Qpow(n, k - i) * s[i] % mod * f[i] % mod;
		upd(ans2, tmp);
	}
	ans2 = ans2 * Inv(Qpow(n, k)) % mod;
	upd(ans, mod - ans2);
	printf("%lld\n", ans);
	return 0;
}