乒乓球

1. 统一建模

记分差

$$d=\text{score}_P-\text{score}_Q$$

初始 $d=0$，到达 $d=n$ 表示 P 获胜，到达 $d=-n$ 表示 P 失败。

定义

$$f(d,i)$$

表示当前分差为 $d$，下一回合使用 $S_i$（为了表述方便，$S$ 下标改为 $0\le i<m$）发球时，最终 P 获胜概率。

令：

• 若 $S_i=\texttt{'P'}$，$a_i=p=\frac{p_a}{p_b}$；
• 若 $S_i=\texttt{'Q'}$，$a_i=q=\frac{q_a}{q_b}$；
• $b_i=1-a_i$。

转移：

$$f(d,i)=a_i\,f(d+1,(i+1)\bmod m)+b_i\,f(d-1,(i+1)\bmod m) $$

边界：

$$f(n,i)=1,\quad f(-n,i)=0$$

答案是 $f(0,0)$。

数据生成方式为随机是为了在计算过程中不会出现在模意义下存在多解。

2. 分 Subtask 对应做法

Subtask 1（$n\le1$）

这一档部分分实际就是 $n=1$。比赛一回合就会结束，答案就是首回合 P 赢球概率：

• 若 $S_0=\texttt{'P'}$，答案 $=p$；
• 否则答案 $=q$。

复杂度：$O(1)$（认为计算逆元为常数复杂度）。

对应代码：std/subtask1.cpp

Subtask 2（$n\le10,\sum m\le20$）

把所有 $-n<d<n$ 的 $(d,i)$ 作为未知数，直接列方程组（包含 $(2n-1)m$ 个未知数以及 $(2n-1)m$ 个包含未知数的等式），高斯消元。

复杂度：

$$O\big((nm)^3\big)$$

对应代码：std/subtask2.cpp

Subtask 3（$m=1$）

退化为一维随机游走。设每回合 P 赢概率 $u$、输概率 $v=1-u$，则

$$f_d=u f_{d+1}+v f_{d-1}$$

配合边界可得

$$f_0=\frac{1}{1+(v/u)^n}$$

快速幂计算。

复杂度：$O(\log n)$。

对应代码：std/subtask3.cpp

Subtask 4（$m=2$）

设

$$A_d=f(d,0),\ B_d=f(d,1)$$

构成 4 维状态

$$V_d=[A_d,B_d,A_{d-1},B_{d-1}]^T$$

得到常系数递推 $V_{d+1}=TV_d$（$4\times4$ 矩阵），矩阵快速幂求解。

复杂度：$O(\log n)$。

对应代码：std/subtask4.cpp

Subtask 5（$n\le10^4,\sum m\le50$）

把 $P_{-n+1}$ 设为 $m$ 个主元，按层传播“线性系数向量”：已知第 $d,d-1$ 层推出第 $d+1$ 层。推到顶层后解一个 $m\times m$ 方程组，再回代求 $f(0,0)$。

复杂度：

$$O(nm^2+m^3)$$

对应代码：std/subtask5.cpp

Subtask 6（满分）

把两层打包：

$$W_d=\begin{bmatrix}P_d\\P_{d-1}\end{bmatrix}\in\mathbb{F}^{2m} $$

存在固定矩阵 $T\in\mathbb{F}^{2m\times2m}$ 使

$$W_{d+1}=TW_d$$

故可用矩阵快速幂处理 $n\le10^{18}$：先由 $W_n$ 上半部分全 1 解出底层未知向量，再算 $W_0$，第一项即答案。

复杂度：

$$O(m^3\log n)$$

对应代码：std/subtask6.cpp