「確率 mod 998244353」とか「期待値 mod 998244353」って何なの？という話 - 徒然

はじめに 分数のmodって何？AtCoderの注釈を読んでも意味わからないんだけど？といった方向けの記事です。 なおこの記事上は法(998244353や1000000007など)が素数であることを前提とします。 結論 結論から言うと、「割り算をするかわりに分母の逆元(モジュラ逆数)をかけて998244353で割った余り」です。 例 実数上の答えがだったとすると、なので、 が有理数mod上での答えとなります。 実際にであることから定義を満たしています。 実装例 Pythonの場合 モジュラ逆数はpow関数で求めることができます。 mod = 998244353 denominator = pow(5926, -1, mod) print(3141 * denominator % mod) # -> 894983505 Python3.7以前では第2引数に負数を与えられないため、mod - 2