ZOJ 3329 One Person Game
令 \(p_i\) 为扔出 \(i\) 分的概率，特殊的，\(p_0\) 为扔出 \((a, b, c)\) 回到分数为 \(0\) 的概率。
考虑倒推，设 \(f_i\) 为达到 \(i\) 分的期望步数，答案即为 \(f_0\)。
\(f_i\) 的转移分为两种：得到更多的分或者是回到 \(0\) 分，于是有转移式子 \(f_i = (\sum\limits_{j = 3}^{k1 + k2 + k3} f_{i + j}\times p_j) + f_0\times p_0 + 1\)。
这个式子看着就很高斯消元的样子，但是太麻烦了，观察式子能发现 \(f_i\) 似乎能表示成 \(a_i\times f_0 + b_i\) 的样子。
于是就可以去推一下式子啦：
首先把 \(f_{i + j}\) 表示为 \(a_{i + j}\times f_0 + b_{i + j}\)：
\(f_i = (\sum\limits_{j = 3}^{k1 + k2 + k3} f_{i + j}\times p_j) + f_0\times p_0 + 1 = (\sum\limits_{j = 3}^{k1 + k2 + k3} a_{i + j}\times f_0\times p_j + b_{i + j}\times p_j) + f_0\times p_0 + 1\)。
然后把 \(f_0\) 提出来：
\((\sum\limits_{j = 3}^{k1 + k2 + k3} a_{i + j}\times f_0\times p_j + b_{i + j}\times p_j) + f_0\times p_0 + 1 = ((\sum\limits_{j = 3}^{k1 + k2 + k3} a_{i + j}\times p_j) + p_0)\times f_0 + (\sum\limits_{j = 3}^{k1 + k2 + k3} b_{i + j}\times p_j) + 1\)。
于是就得到了 \(a_i\) 和 \(b_i\) 的递推式啦：\(a_i = (\sum\limits_{j = 3}^{k1 + k2 + k3} a_{i + j}\times p_j) + p_0, b_i = (\sum\limits_{j = 3}^{k1 + k2 + k3} b_{i + j}\times p_j) + 1\)。
于是可以由 \(n\) 推到 \(0\) 得到 \(f_0 = a_0\times f_0 + b_0\)，解得 \(f_0 = \frac{b_0}{1-a_0}\)。
时间复杂度 \(O(n\times (k1 + k2 + k3))\)。