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

はじめに

分数のmodって何？AtCoderの注釈を読んでも意味わからないんだけど？といった方向けの記事です。
なおこの記事上は法(998244353や1000000007など)が素数であることを前提とします。

結論

結論から言うと、「割り算をするかわりに分母の逆元(モジュラ逆数)をかけて998244353で割った余り」です。

例

実数上の答えが $\frac{3141}{5926}$ だったとすると、 $5926^{-1} \equiv 574251603 \pmod{998244353}$ なので、
$\frac{3141}{5926} \equiv 3141 \times 574251603 = 1803724285023 \equiv 894983505 \pmod{998244353}$ が有理数mod上での答えとなります。
実際に $5926 \times 894983505 = 5303672250630 \equiv 3141 \pmod{998244353}$ であることから定義を満たしています。

実装例

Pythonの場合

モジュラ逆数はpow関数で求めることができます。

mod = 998244353
denominator = pow(5926, -1, mod)
print(3141 * denominator % mod)
# -> 894983505

Python3.7以前では第2引数に負数を与えられないため、mod - 2とすれば求まります。(後述)

mod = 998244353
denominator = pow(5926, mod - 2, mod)
print(3141 * denominator % mod)
# -> 894983505

C++の場合

AtCoder Library (ACL)にinv_mod関数があるため、それを利用できます。
オーバーフローには注意です。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
int main()
{
  int mod = 998244353;
  long long denominator = inv_mod(5926, mod);
  cout << 3141 * denominator % mod << endl;
  // -> 894983505
}

また、Modintを用いて普段の割り算のように計算することもできます。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
int main()
{
  mint ans = 3141;
  ans /= 5926;
  cout << ans.val() << endl;
  // -> 894983505
}

ACLが使えない場合は「c++ 逆元」などで検索すると有志のライブラリが見つかります。

PythonでもModintを使いたい場合は私のライブラリにあるので、それを利用すると良いです。

github.com

class Modint(int):
    mod = 998244353
    # (以下略)

ans = Modint(3141)
ans /= 5926
print(ans)
# -> 894983505

性質

合同式の性質をほぼすべて満たします。*1

manabitimes.jp

例

足し算

$\frac{1}{2} \equiv 499122177, \frac{1}{3} \equiv 332748118 \pmod{998244353}$ なので
$\frac{1}{2} + \frac{1}{3} \equiv 499122177 + 332748118 = 831870295 \equiv \frac{5}{6} \pmod{998244353}$

コインを4回投げてすべて表が出る確率

1回表の確率が $\frac{1}{2} \equiv 499122177 \pmod{998244353}$ なので
4回表の確率は $(\frac{1}{2})^{4} \equiv (499122177)^{4} \equiv 935854081 \pmod{998244353}$
累乗は繰り返し二乗法で求められます。Pythonならpow(底, 冪指数, mod)で、C++ならACLのpow_modやmodint.pow(冪指数)が使えます。

MOD-2の話

$a \ne 0$ のときフェルマーの小定理より $a \equiv a^{P} \pmod{P}$
両辺に $a^{-2}$ をかけて $a^{-1} \equiv a^{P - 2} \pmod{P}$
$a = 0$ のときも上の式に代入すると $P \geq 3$ のとき成立することがわかる。

注意点

階乗が絡むとき

$x \geq P$ のとき、 $x \equiv s \pmod{P}$ となる $s$ が基本的に $a^{x} \not\equiv a^{s} \pmod{P}$ となることを間違えやすいです。
正しくは、フェルマーの小定理より $x \equiv t \pmod{P - 1}$ として $a^{x} \equiv a^{t} \pmod{P}$ となります。

例： $10^{10^{10}} \pmod{998244353}$ を求めよ
$10^{10} \equiv 17556480 \pmod{998244352}$ なので
$10^{10^{10}} \equiv 10^{17556480} \equiv 304046918 \pmod{998244353}$