题目大意

这是一个零和博弈问题：

走私者选择金额 $x \in [0, n]$

检察官猜测金额 $y \in [0, n]$

收益矩阵：

$x = y$：收益 0

$x > y$：走私者得 $x$，检察官失 $x$

$x < y$：走私者得 $y/2$，检察官失 $y/2$

求混合策略纳什均衡。

算法思路

核心思想

线性规划对偶 + 递推求解

数学建模

设走私者以概率 $p_i$ 选择 $i$，检察官以概率 $q_i$ 选择 $i$。

1. 收益函数

对于给定的 $(p, q)$：

走私者期望收益：$\sum_{i=0}^n p_i \left[ i \cdot \sum_{j=0}^{i-1} q_j + \frac{1}{2} \sum_{j=i+1}^n j \cdot q_j \right]$

检察官期望损失（取负收益）：$-\sum_{j=0}^n q_j \left[ \sum_{i=j+1}^n i \cdot p_i + \frac{1}{2} \sum_{i=0}^{j-1} j \cdot p_i \right]$

2. 纳什均衡条件

存在常数 $v$（博弈值）使得：

对于所有 $i$，若 $p_i > 0$，则选择 $i$ 的期望收益 = $v$

对于所有 $j$，若 $q_j > 0$，则选择 $j$ 的期望损失 = $v$

3. 推导解

通过线性规划对偶和对称性分析，可以得到封闭解：

走私者策略

$p_i = \frac{1 + [i=0]}{n+2}$，其中 $[i=0]$ 是指示函数（$i=0$ 时为 1）

检察官策略

通过递推计算：

$f_0 = 1, f_1 = 2$

$f_i = 2^{i-1} \cdot (i+3) \mod (mod-1)$

归一化：$q_i = f_i / \sum_{j=0}^n f_j$

4. 模运算处理

由于概率要对 $998244353$ 取模，使用模逆元进行归一化。

算法流程

读入 $n$

计算走私者策略：

分母 $v = (n+2)^{-1} \mod 998244353$

$p_i = (1 + [i=0]) \times v \mod 998244353$

计算检察官策略：

递推计算 $f_i$

计算总和并求逆元

归一化得到 $q_i$

输出两行概率分布

复杂度分析

时间复杂度：$O(n)$，线性递推

空间复杂度：$O(n)$，存储 $f$ 数组

模运算：使用快速幂求逆元 $O(\log mod)$

数学验证

对于 $n=1$ 的样例：

走私者：$p_0 = 2/3, p_1 = 1/3$

检察官：$q_0 = 1/3, q_1 = 2/3$

验证满足纳什均衡条件

总结

本题展示了：

博弈论建模：将实际问题转化为零和博弈

纳什均衡求解：通过线性规划对偶得到封闭解

递推优化：避免直接求解大规模线性方程组

模运算技巧：在模质数下进行概率计算