ARC174C 题解

标签：cdot 题解 large dfrac Bob ARC174C

blog。官解似乎很难想到，这里是容易想到的方法。

---

显然是 DP。介于轮数可能趋近于无穷，所以类似 P4550 做即可。

设 \(f_i,g_i\) 表示已经抽了 \(i\) 个数，当前是 Alice 或 Bob 抽的，期望罚款。

倒推处理，\(f_n=g_n=0\)。下文中 \(p=\dfrac in\) 表示抽到已经有的概率。

\[\large\begin{cases}f_i=(1-p)\cdot g_{i+1} + p\cdot g_i\\g_i=(1-p)\cdot f_{i+1} + p\cdot(f_i+1)\end{cases} \]

含义：Alice 要么是 Bob 抽完后轮到他，直接抽中新的；要么是没抽中，轮给 Bob。

将 \(f_i\) 代入 \(g_i\)，得：

\[\large\begin{aligned}f_i & =(1-p)\cdot g_{i+1} + p\cdot\Big(f_{i+1} \cdot (1 - p) + (f_i + 1) \cdot p)\Big)\\& = (1-p)\cdot g_{i+1}+p(1-p)\cdot f_{i+1}+p^2+p^2\cdot f_i\end{aligned} \]

移项即有：

\[\large f_i=\dfrac{(1-p)\cdot g_{i+1}+p(1-p)\cdot f_{i+1}+p^2}{1-p^2} \]

\(g_i\) 代入即可，答案即 \(f_1\) 与 \(g_1\)。

code，除去快速幂即 \(O(n)\)。实现时小心爆 long long。

标签：cdot,题解,large,dfrac,Bob,ARC174C
From： https://www.cnblogs.com/liangbowen/p/18082512