導入
概要
本稿では、mod pにおける二項定理を$O(n)$で計算する方法を説明していく。
きっかけは、E869120さんの記事を読んでいく中で、「二項係数への応用（レベル：3）」が全く理解できず、詳しく調べようと思ったからだ。
（アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita）
しかし、調べていく中で、「これを読めば一発で理解できる！！」という記事が中々見つからなかったので、これから競プロで使う二項定理を学ぶ方へ向けて、数学的知見が乏しい筆者が掲題に対する自分の理解を共有できたらと思い、執筆に至った。
※参考サイトは最後に纏めて貼ることとする。
今回扱う問題
本稿では、二項定理の問題の代表としてABC034のC問題を扱うこととする。
一旦問題文に全文を通してみて、解法を考えてみて欲しい。
組み合わせの問題であるため、まずは二項定理${}_n C _r = \frac{n!}{r!(n-r)!} \pmod p$を計算することを考える。しかしながら、この二項定理の計算が厄介で、$n$が大きくなるにつれて$n!$が非常に大きくなってしまうため、計算が出来ない。
ここで、Pythonを例に考えてみよう。
Pythonのint型は、PCのビット数により最大値が決まる。
- 32bit → $2^{31} - 1=2,147,483,647 \qquad\qquad\qquad < 10^{10}$
- 64bit → $2^{63}-1 = 9,223,372,036,854,775,807 < 10^{19}$
次に、$n!$の大きさはどうだろうか。
Wikiを参考にしてみると、23!までの値一覧が掲載されていた。そのうちの一部を抜粋する。
- $20! = 2,432,902,008,176,640,000 < 10^{19}$
- $21! = 51,090,942,171,709,440,000 < 10^{20}$
大きさを比較してみると以下のようになる。
2^{31}-1 < 10^{10} < 20! < 2^{63}-1 < 10^{19} < 21!
高々20程度でPythonが扱える整数型から逸脱する。今回扱う問題では、$n$の最大値は$2 \times 10^{5}$までを想定する必要があるため、二項定理の公式を愚直に計算することはできないことが分かる。
ではどうするのか
では、実際に二項定理を$O(n)$で計算するための方法とは？答えは「mod pであることを利用して、逆元とフェルマーの小定理を使った式変形により、式を計算可能な形にする」である。
実際の式変形がこちら。
\begin{align}
{}_n C _r = \frac{n!}{r!(n-r)!}\pmod p \qquad・・・① \\
\equiv n! \times (r!の逆元) \times ((n-r)!の逆元) \pmod p\qquad・・・② \\
n! \times (r!)^{p-2} \times ((n-r)!)^{p-2} \pmod p\qquad・・・③
\end{align}
①→②→③の式変形を後の章で詳しく説明していこうと思う。
本稿は次のような構成となっている。
（１）逆元とは
（２）$\pmod p$において、フェルマーの小定理を用いて$a$の逆元$b$を求める。
（３）aの逆元の計算量
（４）式変形の再掲、各項の計算量
（５）②と③への式変形について
（６） $n!\times(r!)^{p-2}\times((n-r)!)^{p-2} \pmod p$の計算
説明
（１）逆元とは
逆元とは、とある数bが数aに対して持つ性質のことである。
その性質とは「aにbをかけると１になる」ことである。
例1）逆数と逆元
$a$の逆数$\frac{1}{a}$は逆元である。これは$a \times \frac{1}{a}=1$であることから明らかである。
また、これを初めてこの逆元という概念を見た時、数学の知識がない人（つまり私のことだが）は「逆数以外に逆元は存在しないのでは？」という疑問を持つ。
しかしながら、$\pmod p$の世界では問題においては、逆数以外の逆元が存在することがあるのだ。
例2）逆数以外の逆元
例えば、$\pmod p$であるとき、$2$は$3$の逆元であるか？
実際に計算をしてみよう。
$3 \times 2 = 6 ≡ 1 \pmod p$となり、$2$は$3$の逆元である。
このことから、$\pmod p$においては$3$の逆元は無限に存在する（$2, 7, 12,$ … ）。
（２） mod pにおいて、フェルマーの小定理を用いてaの逆元bを求める。
では、$\pmod p$における逆元を実際にどうやって求めるのか。
ここで、フェルマーの小定理を導入する。
- フェルマーの小定理
a^{p-1} \equiv 1 \pmod p \quad
※フェルマーの小定理は数学的帰納法で証明できるが、ここではその証明を省きたく思う。参考サイトに記事を載せているので、参考にしてほしい。
ここで、この小定理の両辺に$a \times a^{-1}$を掛ける（ただし、ここでの$a^{-1}$は、逆数としての記法ではなく指数としての記法であることに気を付けること）。
\begin{align}
a^{p-1} \times a \times a^{-1} \equiv 1 \times a \times a^{-1} \pmod p \\
\implies a \times a^{p-2} \equiv 1 \pmod p ・・・ （A）
\end{align}
（A）の式が主張しているのは、「$a$に$a^{p-2}$を掛けると1になる」、すなわち「$a^{p-2}$は$a$の逆元である」ということである。
（３）aの逆元の計算量
ここまでで、$\pmod p$において$a$の逆元が$a^{p-2}$であることまでは分かった。
$a^{p-2}$は繰り返し二乗法により、$O(\log{p})$で求められることが知られている。
今回は詳しく立ち入らないが、気になる方は以下の記事を参考にしてほしい（そのうちちゃんと説明を記述するかも）。
（参考：https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b）
ちなみに、Pythonのpow(a, b)は繰り返し二乗法で実装されている。
（４）式変形の再掲、各項の計算量
$\pmod p$である二項定理の式は、以下のように変形できる。
\begin{align}
{}_n C _r = \frac{n!}{r!(n-r)!}\pmod p ・・・① \\
\equiv n! \times (r!の逆元) \times ((n-r)!の逆元) \pmod p・・・② \\
\equiv n! \times (r!)^{p-2} \times ((n-r)!)^{p-2} \pmod p・・・③
\end{align}
※$r!の逆元、(n-r)!の逆元$はそれぞれ$(r!)^{-1}$、$((n-r)!)^{-1}$と表現できるらしいが、数学をあまり嗜まない私が初見で見た時に指数と混同してしまったため、分かりやすさのために前者の記載をしている
ここで、計算量は以下のようになる。
- $n!\pmod p$ の計算量 ＝ $O(n)$
- $(r!)^{p-2}\pmod p$の計算量 ＝ $O(\log{(p-2)})$
- $((n-r)!)^{p-2}\pmod p$の計算量 ＝ $O(\log{(p-2)})$
#（５）②と③への式変形について
■①→②について
${}_n C _r = \frac{n!}{r!(n-r)!}\pmod p$ ・・・① \quad
①の両辺に対して$r! \ \times (r!の逆元)$と$(n-r)! \times ((n-r)!の逆元)$を掛けることを考える。
「$b$が$a$の逆元であるとは、$a \times b = 1$である」ことなので、
・$r! \times (r!の逆元)=1$
・$(n-r)! \ \times ((n-r)!の逆元)=1$
である。つまり、①の左辺に変化はないため、①の右辺を変形していく。
\begin{align}
①の右辺 \implies \frac{n!}{r!(n-r)!}\times r! \times (r!の逆元) \times (n-r)! \ \times ((n-r)!の逆元)\pmod p \\
\implies \frac{n!}{(r!)(n-r)!}\times r! \times (r!の逆元) \times (n-r)! \ \times ((n-r)!の逆元)\pmod p \\
\implies\quad\quad n!\qquad\times \qquad(r!の逆元) \times\qquad\qquad\quad ((n-r)!の逆元)\pmod p
\end{align}
よって、②の式が成り立つ。
\frac{n!}{r!(n-r)!}\equiv n! \times (r!の逆元) \times ((n-r)!の逆元) \pmod p \quad ・・・②
■②→③について
フェルマーの小定理から導いた（A）の式より、
- $(r!の逆元) ＝ (r!)^{p-2}$
- $((n-r)!の逆元) ＝ ((n-r)!)^{p-2}$
であるため、②の右辺をそのまま置換することで③の式となる。
\quad n! \times (r!の逆元) \times ((n-r)!の逆元) \equiv n! \times (r!)^{p-2} \times ((n-r)!)^{p-2} \pmod p・・・③
■纏め
以上より、mod pの二項定理は次のように表せる。
{}_n C _r \equiv n! \times (r!)^{p-2} \times ((n-r)!)^{p-2} \pmod p
（６）③の計算
では実際に、C - 経路 (atcoder.jp)を解いていこう。
方針としては以下の通り。
- $0! ～n! \pmod p$の値を格納したリスト$L$（長さ$n+1$）を作成する。
- $L[r] = r!$、$L[n-r] = (n-r)!$であるため、$(L[r])^{p-2} \pmod p$、$(L[n-r])^{p-2} \pmod p$を繰り返し二乗法を使って計算。
- （1と2で計算した値をすべて掛け合わせた値）$mod\quad p$ が答えとなる。
ということで、下記がPythonで実装したコード。問題なくACしました。
提出 #42867390 - AtCoder Beginner Contest 034
所感
E869120さんの記事からスタートしていろいろと文献を当たりましたが、中でも直大さんの解説が初学者向けでとてもわかりやすかった。流石です…。
また、本稿には数式が多分に含まれていますが、QiitaのTex記述にて、以下の点で困りました。
- 見出しでTexの数式が使えない
- \cancelが使えない（割り算の打ち消しを行うときの記法）
help me 有識者。
ということで、ここまでお読み頂きありがとうございました！
参考記事
- ABC034_C問題：C - 経路 (atcoder.jp)
- ABC034_C問題の解説：Microsoft PowerPoint - abc034-160312140607 (atcoder.jp)
- E869120さん記事：https://qiita.com/e869120/items/b4a0493aac567c6a7240
- PythonのInt型の最大値：https://docs.python.org/ja/3/library/sys.html#sys.maxsize
- 階乗について：https://ja.wikipedia.org/wiki/階乗
- フェルマーの小定理の証明：https://manabitimes.jp/math/680
- 繰り返し二乗法：https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b