ABC280E 题解

sto_5k_orz · 2023-03-31 17:20:11 · 题解

首先，求逆元可以使用费马小定理。

设 \dfrac{a}{b}\equiv x\pmod p

则根据费马小定理，b^{p-1}\equiv 1\pmod p，

所以 \dfrac{a}{b}\times b^{p-1}\equiv 1x\pmod p

化简，得 \dfrac{a}{b}\equiv a\times b^{p-2}\pmod p。

详见 P2613

接下来，考虑设状态。

令 dp_i 表示打掉 i 的血的期望步数。

那么 dp_i 可以分类讨论，由 i-1 到 i 的可能性是 p\%，由 i-2 到 i 的可能性是 (100-p)\%。

那么 dp_i=dp_{i-1}\times p\%+dp_{i-2}\times (100-p)\%。

注意初始化，dp_0=0,dp_1=1。

为了计算逆元，dp 数组要边转移变求逆元。

剩下的代码就很没用必要了吧，都分析到这了。