HDU1204糖果大战题解

这篇题解写的很不错，但是一些小细节我还是太看不懂了，所以补充一下。
【首先得注意到是胜者从败者中拿走一颗糖。】
首先 simple 地设 $f_i$ 表示当 S 有 $i$ 颗糖的时候获胜的概率。那么边界条件显然：$f_0=0,f_{n+m}=1$。

由题意得到，一局游戏中，S 赢的概率为 $p(1-q)$，G 赢的概率为 $q(1-p)$，平局的概率为 $1-p(1-q)-q(1-p)$。

此时我突发奇想：平局的概率会不会是个负数？
于是开始证明 $1-p(1-q)-q(1-p) \ge 0(0 \le p,q \le 1)$。
$1-p(1-q)-q(1-p)=1-(p+q)+2pq=1-(p+q-2pq)$
$\because p+q \ge 2\sqrt{pq} \therefore p+q-2pq \ge 2\sqrt{pq}-2pq=2\sqrt{pq}(1-\sqrt{pq})$
当且仅当 $p=q$。
此时 $p+q-2pq =2\sqrt{pq}(1-\sqrt{pq})=2p(1-p)$，当 $p=0/1$ 时取 $\min=0$，当 $p=0.5$ 时取 $\max=0.5$。
$\therefore 1- \dots $ 的 $\min=0.5,\max=1$。
OK 证毕。

返回正题，尝试写出 DP 转移方程得到 $f_i=f_{i+1} \times p(1-q)+f_i \times (1-p-q+2pq)+f_{i-1} \times q(1-p)$。

\[f_i \times (p(1-q)+q(1-p))=f_{i+1}\times p(1-q)+f_{i-1}\times q(1-p) \]

\[(f_i-f_{i-1}) \times q(1-p)=(f_{i+1}-f_i)\times p(1-q) \]

设 $g_i=f_i-f_{i-1}$，则 $g_i \times q(1-p)=g_{i+1}\times p(1-q)$。
$\therefore \dfrac{g_{i+1}}{g_i}=\dfrac{q(1-p)}{p(1-q)}$。
我们得到了一个很重要的性质：$f$ 数组的差分数组是等比数列！！！
啊哈哈哈哈哈哈 Maly 也是出息了。
【以后记这个长长的公比为 $k$。】

我们需要分类讨论一下。
如果 $\dfrac{q(1-p)}{p(1-q)}=1$，即 $q-pq=p-pq \rightarrow q=p$，那么 $g$ 数组都相等。
我们有一个结论，此时 $f_n=\dfrac{n}{n+m}$。
为什么呢？
我们回到最开始的式子，$f_i \times (p(1-q)+q(1-p))=f_{i+1}\times p(1-q)+f_{i-1}\times q(1-p)$。
把 $p=q$ 代入得到 $$f_i \times (2p(1-p))=f_{i+1}\times p(1-p)+f_{i-1}\times p(1-p)$$

\[2f_i=f_{i+1}+f_{i-1} \rightarrow f_{i+1}-2f_i+f_{i-1}=0 \]

这是一个并不典型的“二阶线性差分方程”。
引用 Deepseek 的原话来解释。

什么是差分方程？

差分方程是描述序列值之间关系的方程，类似于微分方程，但处理的是离散变量（如整数 $n$）。在本问题中，$f(n)$ 表示当 S 有 $n$ 颗糖果时获胜的概率，它是一个离散函数。

什么是二阶线性差分方程？

二阶：表示方程中涉及序列的“第二阶差分”，即同时包含 $f(n+1)$、$f(n)$ 和 $f(n−1)$ 项。直观上，它描述了当前状态与前后两个状态之间的关系。

线性：表示方程中 $f(n)$ 及其差分项都是以线性形式出现的（没有像 $f(n) ^2$ 这样的非线性项）。

齐次：表示方程右边等于零（即没有常数项或其他驱动项）。

如何求解这类方程？

对于二阶线性齐次差分方程，通解通常通过特征方程法找到。

假设解的形式为 $f(n)=r^n$，代入方程：
$r^{n+1}−2r^n+r^{n−1}=0$

除以 $r^{n−1}$（假设 $r \neq 0$），得到 $r^2−2r+1=0$，解得 $r_1=r_2=1$。

因此通解为 $f(n)=A+Bn$。其中 $A$ 和 $B$ 是常数，由边界条件确定。

什么叫“特征方程法”？这又是另一个故事了。【本来二阶线性差分方程就是另一个故事。】

原本 $f(i)$ 的通解为 $f(i)=Ar_1^n+Br_2^n$。
因此 $af(i+1)+bf(i)+cf(i-1)=0$

\[a(Ar_1^{i+1}+Br_2^{i+1})+b(Ar_1^i+Br_2^i)+c(Ar_1^{i-1}+Br_2^{i-1})=0 \]
拆开后得到：

\[a(Ar_1^{i+1})+b(Ar_1^i)+c(Ar_1^{i-1})=0 \]
\[a(Br_2^{i+1})+b(Br_2^i)+c(Br_2^{i-1})=0 \]
全部除以 $x^{i-1}$得到：

\[A(ar_1^2+br_1+c)=0 \]
\[B(ar_2^2+br_2+c)=0 \]
于是把 $a,b,c$ 代入就可以解出两个解了。然后再回代。