自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:45:45，当前版本为作者最后更新于2023-03-20 16:33:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设走私者放 $i$ 元的概率为 $f(i)$，检察官猜 $i$ 元的概率为 $g(i)$，则：

• 走私者放 $i$ 元时，走私者的期望收益为 $E_1(i) = i \displaystyle\sum_{j = 0}^{i - 1} g(j) + \frac{1}{2} \sum_{j = i + 1}^n j g(j)$。
• 检察官猜 $i$ 元时，走私者的期望收益为 $E_2(i) = \frac{i}{2} \displaystyle\sum_{j = 0}^{i - 1} f(j) + \sum_{j = i + 1}^n j f(j)$。

这里我们以第一个式子为例（第二个式子的后续推导与之相似）。

下面是一个小但我之前不会的套路。

注意到“你需要保证，在一方的策略不变的情况下，另一方无论如何改变自己的策略，都不能使自己的期望收益比原来多。”，考虑调整法，设 $\Delta g(i) = g'(i) - g(i)$ 表示对走私者策略进行调整的幅度——显然有 $\displaystyle\sum_{i = 0}^n \Delta g(i) = 0$。

然后有 $\displaystyle\sum_{i = 0}^n \Delta g(i) E_1(i) \leq 0$ 恒成立。假如我们抓出 $E_1(i)$ 中最大者并给它整一个很大的 $\Delta g(i)$，若此时 $E_1(i)$ 不两两相等，则一定存在一种 $\Delta g(i)$ 使之不合法，于是我们得出了本题最关键的结论：

• $E_1(i)$ 两两相等。

考虑抓出比较像的相邻两项来讨论，下面假定我们讨论 $E_1(i) = E_1(i + 1)$：

• $i \displaystyle\sum_{j = 0}^{i - 1} g(j) + \frac{1}{2} \sum_{j = i + 1}^n j g(j) = (i + 1) \sum_{j = 0}^i g(j) + \frac{1}{2} \sum_{j = i + 2}^n j g(j)$。

进行化简后可得：

• $g(i) = \dfrac{2((i - 1) g(i - 1) + \displaystyle\sum_{j = 0}^{i - 1} g(j))}{i}$。

于是我们可以将所有 $g(i)$ 表示为 $g(0)$ 的倍数，又因为 $\displaystyle\sum_{i = 0}^n g(i) = 1$，我们将系数代入求出 $g(0)$ 即可得出所有 $g(i)$。

同理可得：$f(i) = \dfrac{(i - 1) f(i - 1) + \displaystyle\sum_{j = 0}^{i - 1} f(j)}{2i}$。

线性求逆即可。时间复杂度为 $O(n)$。

代码：

#include <stdio.h>

typedef long long ll;

const int mod = 998244353;
ll inv[800007], f[400007], g[400007];

inline void init(int n){
	inv[0] = inv[1] = 1;
	for (register int i = 2; i <= n; i++){
		inv[i] = mod - (mod / i) * inv[mod % i] % mod;
	}
}

inline ll quick_pow(ll x, ll p, ll mod){
	ll ans = 1;
	while (p){
		if (p & 1) ans = ans * x % mod;
		x = x * x % mod;
		p >>= 1;
	}
	return ans;
}

int main(){
	int n;
	ll pre = 0, sumf = 0, sumg = 0;
	scanf("%d", &n);
	init(n * 2);
	f[0] = 1;
	for (register int i = 1; i <= n; i++){
		pre = (pre + f[i - 1]) % mod;
		f[i] = (f[i - 1] * (i - 1) % mod + pre) % mod * inv[i * 2] % mod;
	}
	for (register int i = 0; i <= n; i++){
		sumf = (sumf + f[i]) % mod;
	}
	sumf = quick_pow(sumf, mod - 2, mod);
	for (register int i = 0; i <= n; i++){
		printf("%lld ", f[i] * sumf % mod); 
	}
	printf("\n");
	pre = 0;
	g[0] = 1;
	for (register int i = 1; i <= n; i++){
		pre = (pre + g[i - 1]) % mod;
		g[i] = (g[i - 1] * (i - 1) % mod + pre) % mod * 2 % mod * inv[i] % mod;
	}
	for (register int i = 0; i <= n; i++){
		sumg = (sumg + g[i]) % mod;
	}
	sumg = quick_pow(sumg, mod - 2, mod);
	for (register int i = 0; i <= n; i++){
		printf("%lld ", g[i] * sumg % mod); 
	}
	return 0;
}