CWOI S C0299 B 游戏

题意

U2FsdGVkX1/pi5f7t8aHT6ehMwunDIhi00NvSoe4aCyZ8Fk8m2vFi3hWW5OO4vDp
MfwFbI3sQrzVHrUgGjrAFjdnLXrTZUp4BXdhblhn+RcM8m9EqO9d5JSr+w6rwjoe
pDWYdgA706Gsr+xsDuVVIQ1DWnMWjYWhff16vYtBLjjPpHCNHMJF+0i9MGKTk0D0
csdHnIg8LGMLGsd7ji7UX9jTmzrhYVpn4u0nlCSmkVxM2kBgzZP9nZOYYfQqPcsb
7Q9G02djyeeIr8/RfcPTViRvjEOXrrHRE2+spTcGV88bWdBr+wbqgVudTlU1pcvb
lQVdZEYXTj4RCfFAelJ83Qz/yQmEWTB4O65fW0RTqIIY4zjMTgWEMVtGgRtYvXwA
NI0KpXDQo3vtIQOCMBM/B/iSdWjSjhxSfInmzWj1JA79yew4qe/rADARl6G46vOv
AkDBE5/qVlOiSegDEPN6cyz+L1EVLSecDR7NlgRGdyY=

解析

首先，这个期望可以表示成：$\sum_{i=1}^{k} i \times P(i)$，其中 $P(i)$ 表示在第 $0$ 刚好在第 $i$ 次操作被删掉的概率。考虑令 $P'(i) = \sum_{j=i}^{k}P(i)$，即在第 $i$ 次操作还没移除 $0$ 的概率，然后这个期望就可以表示成：$\sum_{i=1}^{k} P'(i)$。我们的任务就变成了求解 $P'(i)$。

令 $f(i, j)$ 表示，考虑前 $i$ 个棋子，已经操作了 $j$ 次的概率。由于我们要求 $0$ 处的棋子没有被移除，那么对于任意 $i$，$0$ 到 $i$ 至多被操作 $i-1$ 次，否则就会把 $1$ 移除。可以得到转移方程：

$$f(i, j) = \sum_{k=0}^{j} f(i - 1, j - 1) \times \binom{j}{k} \times \left(\frac{s_{i}}{n}\right)^k$$

其中，$s_{i}$ 是第 $i$ 个棋子到第 $i+1$ 个棋子中间的距离。

最后，答案就是 $\sum_{i=0}^{k} f(k, i)$。

实现

int main()
{
	set_io("game");

	int n, k;
	std::cin >> n >> k;
	std::vector<int> a(k), s(k);
	for (auto &i : a) {
		std::cin >> i;
		i--;
	}

	for (int i = 0; i < k; i++) {
		s[i] = ((a[(i + 1) % k] - a[i]) % n + n) % n;
	}

	std::vector<mint> fact(k + 1), ifact(k + 1);
	fact[0] = 1;
	for (int i = 1; i <= k; i++) fact[i] = fact[i - 1] * i;
	ifact[k] = fact[k].inv();
	for (int i = k; i >= 1; i--) ifact[i - 1] = ifact[i] * i;
	auto binom = [&fact, &ifact](int n, int m) -> mint
	{
		if (m < 0 || m > n) return 0;
		return fact[n] * ifact[m] * ifact[n - m];
	};

	mint INVN = mint{n}.inv();
	std::vector<mint> f(k + 1);
	f[0] = 1;
	mint ans = 0;
	for (int i = 1; i < k; i++) {
		std::vector<mint> g(k + 1);
		mint base = mint{s[i]} * INVN;
		for (int j = 0; j < i; j++) {
			mint pow = 1;
			for (int t = 0; j + t <= i; t++) {
				g[j + t] += f[j] * binom(j + t, t) * pow;
				pow *= base;
			}
		}
		f = std::move(g);
	}

	for (int j = 0; j <= k; j++) {
		ans += f[j];
	}

	std::cout << ans.val() << std::endl;
}