逆元を知らない人でも確率dp mod 998244353を通せるようにするための「おまじない」(茶~緑向け)

せっかくブログを立てたので競プロの記事を書きます。

dp などの問題で確率 mod P (P は大きい素数)を求めることがしばしばあります。
初見だと「は?確率の mod?何いってんだこいつ」となりがちなので、この記事では

単純なナップサック dp のような D 問題相当の dp なら解けるけど、確率 mod P とか言われると「は?何いってんだこいつ」となる人向けに

  1. Python ユーザーが ACL の modint に相当するライブラリ等を使わずに
  2. 答えが小数になることを許容してそのまま実装し
  3. 実装した確率 dp を機械的に mod P に対応させる

というステップで解く方法について整理しました。