Mod（剰余算）
1．剰余算（モジュロ）の基本
加法（＋），減法（ー），乗法（×）については，いつ行っても結果は同じ．
除法（÷）は「できない」と考えよう（厳密には「できる」場合もあるが）
扱う数が大きくなりそうなら，常にMODを取る心構えで．
２．剰余算の逆元
除法（÷）の代わりに，逆元を掛けよう（行列演算における逆行列のイメージ）
まーす.icon注釈を付けときます．詳しいことは代数学（３年次履修）で学習します．予習したい方は，「群」，「環」，「体」というワードで検索かけてください．このページでは「$ p が素数 \Rightarrow \mathbb{Z}_{p}は体」という事実を利用しているので，「群」→「体」の順で検索かけることをお勧めします．本来の数学での定義の仕方とは異なる順番で紹介しますが，「そんなものがあるんだぁ～」程度で思っておいてください．
代数（数学的）な意味での逆元は$ (S,\ \cdot) を代数系として，$ \forall a \in S,\ \exists a ^ {-1} \in S,\quad a \cdot a ^ {-1} = a ^ {-1} \cdot a = e. ただし，ここでの$ eは$ Sの単位元を表す．
例１．実数全体$ \mathbb{R}と演算$ +の組$ (\mathbb{R},\ +)の逆元は$ \forall a \in \mathbb{R}に対して，$ - aである．
例２．実数全体から$ 0を除いた集合$ \mathbb{R} - \{0\}と演算$ \timesの組$ ( \mathbb{R} - \{0\},\ \times)の逆元は$ \forall a \in \mathbb{R}に対して，$ a ^ {-1}である．
代数系とは，集合$ Sに対して演算$ \cdotが定義されていて，$ \forall a,\ b \in S,\quad a \cdot b \in Sとなるものの組$ (S,\ \cdot)のことを指します．
単位元とは，$ \exists e \in S,\ \forall a \in S,\quad e \cdot a = a \cdot e = aを満たしたときの$ eを指します．
例１．実数全体$ \mathbb{R}と演算$ +の組$ (\mathbb{R},\ +)の単位元は$ 0 \in \mathbb{R}である．
例２．実数全体から$ 0を除いた集合$ \mathbb{R} - \{0\}と演算$ \timesの組$ ( \mathbb{R} - \{0\},\ \times)の単位元は$ 1 \in \mathbb{R}である．
逆元を求めるには，フェルマーの小定理を使う（が，理解しなくてもOK）．
フェルマーの小定理： (1)$ pが素数 (2) $ pと$ a が互いに素のとき，次式が成立する．
$ a^{p-1} \equiv 1 \quad ({\rm mod}\ p)\quad \Longleftrightarrow a\cdot a^{p-2} \equiv 1\quad ({\rm mod}\ p)
よって，mod $ pで割り算をしたいとき，$ a で割る代わりに$ a^{p-2} を掛ける
code: python
MOD = 998244353
a_inv = pow(a, MOD - 2, MOD) # 第3引数を指定して，a^{p - 2} (mod p) を計算する
Fermatの小定理では，「pが素数」という制約がある．（その分実装は楽）
pが素数じゃないけど逆元を求めたい場合は，拡張 Euclid の互除法を用いて求めることが可能
３．累乗の剰余算
pow関数で第3引数を指定すると，累乗にMOD演算を行う．
累乗を計算してからMODを取るのではなく，累乗計算過程でMODを取るので，値が大きくならず，TLEを避けられることができる．
$ pが大きいと，$ a^{p-2}の計算に時間がかかるため，「繰り返し2乗法」という方法で計算時間短縮を図るのが一般的．Pythonではpow関数でも**演算でも，内部で繰り返し2乗法を実行しているそうなので，$ pの大きさは気にしなくてよさそう．
４．分数の剰余算
$ b/a\ ({\rm mod}\ p)で$ pが素数でない場合，または$ pと$ aが互いに素でない場合は，フェルマーの小定理の方法では計算できない．
$ b/aが整数のとき，$ \frac{b}{a}\ ({\rm mod}\ p) = \frac{b\ ({\rm mod}\ ap)}{a}が成立する．
５．（参考）整数除算と剰余算
Pythonには整数除算と剰余算と同時に行う関数 divmodがあります．一行で済んで便利？
code: python
a, b = divmod(10, 3) # a = 3, b = 1
参考サイト