P9142 [THUPC 2023 初赛] 欺诈游戏
题面
这个游戏名叫《走私游戏》。游戏规则大概是这样的：一名玩家扮演走私者，一名玩家扮演检察官。走私者可以将 \(x\) 日元（\(x\) 为 \([0,n]\) 内的整数，由走私者决定）秘密放入箱子中，而检查官需要猜测箱子中的金额。假设检察官猜了 \(y\)（\(y\) 也必须是整数）。如果 \(x=y\)，则走私失败，走私者一分钱也拿不到。如果 \(x>y\)，则走私成功，走私者可以从检查官那里拿走 \(x\) 日元。如果 \(x 可以证明，最优情况下每个回合走私者会采用同一种策略，检察官也会采用同一种策略。小 E 想知道在一个回合中，双方的最优策略分别是什么。 题解 混合策略纳什均衡（MNE）模型。 双方当前策略期望 \(u_1(a_1, a_{-1}), u_2(a_2, a_{-2})\) 相等，不存在一方策略调整后能更优。 构建出收益矩阵： \(\text{x\y}\) \(0\) \(1\) \(2\) \(\ldots\) \(n - 1\) \(n\) \(0\) \(0\) \(\frac{1}{2}\) \(1\) \(\ldots\) \(\frac{n - 1}{2}\) \(\frac{n}{2}\) \(1\) \(1\) \(0\) \(1\) \(\ldots\) \(\frac{n - 1}{2}\) \(\frac{n}{2}\) \(2\) \(2\) \(2\) \(0\) \(\ldots\) \(\frac{n - 1}{2}\) \(\frac{n}{2}\) \(\ldots\) \(\ldots\) \(\ldots\) \(\ldots\) \(\ldots\) \(\ldots\) \(\ldots\) \(n - 1\) \(n - 1\) \(n - 1\) \(n - 1\) \(\ldots\) \(0\) \(\frac{n}{2}\) \(n\) \(n\) \(n\) \(n\) \(\ldots\) \(n\) \(0\) 设玩家一选择 \(x = i\) 策略的概率为 \(p_i\)，玩家二选择 \(y = i\) 策略的概率为 \(q_i\)，对于任意策略下期望是列出： \[E_p(i) = (i - 1)\sum_{j = 0}^{i - 1}p_j + \sum_{j = i + 1}^{n}jp_j \] \[E_q(i) = i\sum_{j = 0}^{i - 1}q_j + \sum_{j = i + 1}^{n}\frac{j}{2}q_j \] 由于任意策略期望相等，对相邻两项作差有： \[ip_i = \frac{1}{2}\sum_{j = 0}^{i - 1}p_j + \frac{i - 1}{2}p_{i - 1} \] \[\frac{i}{2}q_i = \sum_{j = 0}^{i - 1}q_j + (i - 1)q_{i - 1} \] 化简可得： \[p_i = \frac{\sum\limits_{j = 0}^{i - 1}p_j + (i - 1)p_{i - 1}}{2i} \] \[q_i = \frac{2\sum\limits_{j = 0}^{i - 1}q_j + 2(i - 1)q_{i - 1}}{i} \] 设 \(p_0\) 具有系数 \(1\)，递推算出所有概率的系数即可。 参考代码 #include using namespace std; typedef long long ll; const int N = 4e5 + 10, mod = 998244353; int n; ll p[N], q[N], inv[N]; ll ksm(ll a, ll k) { ll res = 1; while (k) { if (k & 1) res = res * a % mod; k >>= 1; a = a * a % mod; } return res; } int main() { cin >> n; inv[1] = 1, p[0] = q[0] = 1; for (ll i = 2; i <= max(2, n); i ++ ) inv[i] = mod - mod / i * inv[mod % i] % mod; ll sump = 1, sumq = 1; for (int i = 1; i <= n; i ++ ) { p[i] = (sump + (i - 1) * p[i - 1]) % mod * inv[2] % mod * inv[i] % mod; q[i] = (sumq + (i - 1) * q[i - 1]) % mod * 2 * inv[i] % mod; (sump += p[i]) %= mod, (sumq += q[i]) %= mod; } sump = ksm(sump, mod - 2), sumq = ksm(sumq, mod - 2); for (int i = 0; i <= n; i ++ ) cout << (p[i] * sump % mod) << " \n"[i == n]; for (int i = 0; i <= n; i ++ ) cout << (q[i] * sumq % mod) << " \n"[i == n]; return 0; }
