CF891E Lust

Posted on | Edited on | Views:

指数型生成函数.

给定 $n$ 个数 $a_1,a_2,\dots ,a_n$ 和一个初值为 $0$ 的计数器 $cnt$ ,执行以下操作 $k$ 次:
在 $1,2,\dots,n$ 中等概率随机选择一个数 $i$ ,令 $cnt$ 加上 $\prod_{j\neq i}a_j$，然后把 $a_i$ 减 $1$ .
求 $k$ 次操作后计数器 $cnt$ 的值的期望模 $10^9+7$ .
$n\le 5\times 10^3, k\le 10^9$ .

考虑每次的贡献是 $\prod_{j\neq i} a_j$ ,然后将 $a_i$ 减掉 $1$ ,这可以看成是 $\prod_j a_j-\prod_j a_j’​$ ,即减掉前后所有数乘积之差.

$k$ 次操作的贡献会抵消成 $\prod a_i-\prod (a_i-b_i)$, 其中 $b_i$ 表示 $a_i$ 这个数被在 $k$ 次操作中一共被减了多少次.

前面的乘积是确定的,只用算后面那个乘积的期望,可以写出这个问题的 EGF,

$$
F_a(x)=\sum \frac{a-i}{i!}x^i=e^x(a-x)\\
G(x)=\prod_{i=1}^n F_{a_i}(x)=e^{nx}\prod_{i=1}^n(a_i-x)
$$
所求即为 $\frac{k!}{n^k}[x^k]G(x)$ , 可以暴力求出 $\prod_{i=1}^n(a_i-x)$ 每项系数,再考虑每一项与 $e^{nx}$ 卷积对答案贡献即可.

时间复杂度 $O(n^2)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 5e3 + 10;
int n, k, prod[N], ans = 1;
int main()
{
	n = read(), k = read();
	prod[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		int a = read();
		ans = mul(ans, a);
		for (int j = i - 1; j >= 0; --j)
		{
			inc(prod[j + 1], P - prod[j]);
			prod[j] = mul(prod[j], a);
		}
	}
	int t = 1, inv = fpow(n, P - 2), pw = 1;
	for (int i = 0; i <= n && i <= k; ++i)
	{
		inc(ans, P - mul(mul(t, pw), prod[i]));
		t = mul(t, k - i);
		pw = mul(pw, inv);
	}
	write(ans, '\n');
	return 0;
}