数学嫌いの「逆元を使った二項係数の計算」の説明の練習

競プロを始めたばかりで、AtCoderで必要になった二項係数を$10^9+7$で割った余りの計算がわからないと調べていたところ、けんちょん氏のブログをはじめいくつも分かりやすい記事があったのですが、その中でも数学が苦手な私からすると、うん？とすぐにはいまひとつよくわからないところがちらほらあったので、復習も兼ねて、初学者たる私がつまづいたところを中心に計算方法と原理を書いてみようと思いました。
数学的に厳密な議論ができるとはあまり思えないので、もし万が一これを読んでいる数学苦手な同志がいたら、ここに出てきた数学の用語をさらに調べて正しく理解してもらうとか、なんて検索したらいいかの手がかりにする程度の気持ちで見てもらえると。

・勉強させていただいたけんちょん氏の記事
https://drken1215.hatenablog.com/entry/2018/06/08/210000

二項係数の計算の大まかな方針

問題　

${}_nC_k$を素数$p$でわったあまりはいくらか。

これが今回考える問題。いきなり$p$は素数といいましたがAtCoderではmodの法は素数な問題しか見たことがないです($10^9+7$も素数らしい)。さて、先駆者様方の記事を読むと、だいたい
$${}_nC_k = \frac{n!}{k!(n-k)!} = n! \times (k!)^{-1} \times ((n-k)!)^{-1}$$
と書かれています。マイナス1乗......？書き方を変えただけじゃないか、と思ったりするんですがこれはべき乗を表しているのではなくて逆元を表す記号のほうなんですね。だいたい逆元も$x^{-1}$と表すことが多く、記法が衝突しているせいで初学者としては混乱したり。わかってる人にとってはなんの問題もないのでしょうけど。

逆元とは

いきなり逆元というものがでてきましたが、数学の群というものを知らないとなんだそれは、となるでしょうし、知っていたとしてもじゃあどんな演算によるどんな群での逆元なんだ、と初見では謎が深いところではないでしょうか。

群とは

数学の話になりますが、ざっと私の理解している範囲で簡単にいうと、群とは数の集まり（集合）と演算（かけ算とか、たし算のような）の組であって、ある特別な性質をもっているもののことです。詳しいことは調べればたくさん出てきます。ここで群の性質（というか定義）の一つとして、「群のすべての要素は逆元をもつ」というのがあります。
$$$$

ではその逆元とはなにか、ということですが、ざっくりと、ある群の要素a, bがあったとして、「bはaの逆元である」とは、「aにbをかけると1になる」ということです。（もう少しがんばると、1が単位元で、かける、というのがこの群の演算である場合の話です。ここではさらに可換群かのように説明しています。）

逆元の例

$mod\ 5$で考えたとき、$3\times 2 = 6 \equiv 1$であって、「3に2をかけると1になる」となっているので、2は3の逆元であるし、同様に3は2の逆元となる。
（この場合なにが群になっているかというと、$\{1,2,3,4\}$（もっとがんばると1から4のmod 5上での同値類）がmod 5で考えたときの普通のかけ算について群になっています。1, 4はそれぞれ2乗すると1, 16($\equiv$1)となってそれぞれ自分自身が自分の逆元になっています。0は含めません、というのも0になにをかけても0なので逆元がないから。）
$$$$

長くなりましたが、結局最初の式は何をいいたいかというと、
$$\frac{n!}{k!(n-k)!} = n! \times (k!)^{-1} \times ((n-k)!)^{-1}$$
である、つまりわり算をする代わりに逆元のかけ算をするだけで答えがでるよ、しかもそのほうが計算速くできるよ、ということです。ここでの群はなにかというと、1からp-1までの数の集合が、mod p上のかけ算について群だ、ということになります。（なんでかは後回し。）
逆元はなにかというのは上の通りですが、では逆元のかけ算がなぜわり算と同じになるのか、というのはこの場合はある程度簡単に示せます。
$n!$は$k!(n-k)!$でわりきれる、というのはいいとして、長いので$\frac{n!}{k!(n-k)!}$を$a$とします。すると$n!=a\times k!(n-k) !$より、当然mod pで考えても$n!\equiv a\times k!(n-k)!$です。ここで両辺に$k!$と$(n-k)!$の逆元をかけると、$a\equiv n! \times (k!)^{-1} \times ((n-k)!)^{-1}$となり、もとの問題はpでわったあまりをだせ、となっていることからこれが答えです。

逆元は存在するのか

上のほうでmod 5の例をつかって、ほらね、全部の要素に逆元があるでしょ？とやりました。たった今の説明でも$k!$と$(n-k)!$に逆元がある、つまり1からp-1のうちなにかしらをかければどちらもmod pで1になる、ということを前提としていました。ここで、「ほんとにそのような数が1からp-1の間にあるのか？」という不安がでるかもしれません。結論あるんですが、なぜならそれは$x!$は0ではない、かつ1からp-1（のmod p 上での同値類）がmod p上のかけ算について群だから、ということになります。（群は、すべての要素が逆元をもつと定義されています。）
ではなぜそれが群だといえるのか？ということですが、それはpが素数であることによります。
このあたりから私もよくわからなくなってくるのでキーワードだけおいておきますが、一般に、「既約剰余類群」 というものがあって、それは何かというと、
$$(\mathbb{Z}/p\mathbb{Z})^* = \{\bar{a}\in \mathbb{Z}/p\mathbb{Z}\ |\ aとpの最大公約数は1\}$$というようなものです。新たな記号のオンパレードですが要点として$\mathbb{Z}/p\mathbb{Z}$というのは、pを法とする合同式で同じ値となるものを一つとみなして考える世界、のことです。例えばmod 5 で 3 と13 は数としては違いますが、合同式の上では$3\equiv 13$ですから実質同じもので、そのような合同式の上で同じものをすべてひとまとめにして考えている、ということです。そのひとまとめにしたもの、つまり例えば3, 8, 13, 18, ... をひとまとめにして$\bar{3}$と表しています。（これは同値類と呼ばれます。）つまり合同式の性質を考えて、すべての数を$\bar{0}, \bar{1}, \bar{2}, ... , \bar{p-1}$のp個だけにわけてしまえる、ということです。
で、そのような$\bar{a}$であって、aとpが互いに素なものだけを集めたものを 既約剰余類群 とよんで、それは（mod p上の乗法について）群になる、ということなのですが、pが素数、という条件があると、 1からp-1までのすべての数（の同値類）がこの既約剰余類群に含まれる ことになります。これが、$k!$にも$(n-k)!$にも逆元がある根拠だと思います。pが十分大きいのでどちらもpの倍数ではない、つまり$\bar{0}$という既約剰余類群に含まれないグループに入ることはない、よって逆元はある、とそういうことだと思います。これ以外の説明も当然あるとは思いますが。じゃあなぜ既約剰余類群は群なのかとかこれ以上の深い話はもうわかりませんということにします。（とはいえ既約剰余類群が群であることを示す作業自体にすべての要素が逆元をもつことを示すことが含まれますから、結局ここまでの説明ではなにも証明していないことになるんですが、一応すべて逆元があることが保証されているということだけでもわかれば安心かと思い、ここまで書きました。）

逆元を使った二項係数の計算

ここまできたらもう終わりみたいなもんですが、ではそのような逆元があることはわかったと、それをどう計算で使うのかということになります。そのあたりはすでに先駆者様方がわかりやすくお書きになっているので、だいぶはしょってもいいかなと。
流れとして、${}_nC_0$から${}_nC_n$まですべて計算していくのですが、それぞれ$n! \times (k!)^{-1} \times ((n-k)!)^{-1}$のmod p と等しいことをつかいます。つまり$0!$から$n!$までと、その逆元がわかれば、${}_nC_0$から${}_nC_n$が全部計算できることになります。
ここで例えば$n!$の逆元ですが、これを知るには1からnの逆元がすべてわかればいいということになります。なぜなら$$(n!)^{-1} = 1^{-1}\times 2^{-1}\times ...\times n^{-1}$$となるからです。どうしてこうなるかというのは、逆元の定義に戻って考えるとわかります。$(n!)^{-1}$というのは、$n!$にかけると（mod p上で）1になる数のことです。一方右辺は１からnまでの逆元の積ですが、これに$n!$をかけると1からnまでとそれぞれの逆元とがかけあわさってすべて1になるので、結果積は1になります。つまり$n!$にかけて1となる数、であるのでこれは$(n!)^{-1}$そのものということです。
また$k^{-1}$は、1からk-1の逆元をつかって計算できます。まずpをkでわり算することを考えると、商をq、あまりをrとして$p = q\times k + r$とできます。ここでmod pの合同式を考えると$q\times k + r \equiv 0$です。よって$r\equiv - q\times k$ですが、ここで両辺にkの逆元をかけると、$r\times k^{-1} \equiv -q$、さらに両辺にrの逆元をかけて$k^{-1} \equiv -q\times r^{-1}$です。rはkより小さい、かつ0ではありえない（ただしk=1を除く）ので、$r^{-1}$はすでに求まっているはずです。よってkの逆元が計算できました。

以上から

• $k!$
• $k^{-1}$
• $(k!)^{-1}$

を0からnまで計算すれば二項係数はすべて計算できることになります。（ただし上にもある通りk=0,1あたりは初期値として用意しておく必要があります。）これらは3つ並行して計算できると思います。私がPythonで書いたものはこちらになります。

comb.py

def comb(n, k, mod):

    fact = [0] * (n + 1)
    inv = [0] * (n + 1)
    finv = [0] * (n + 1)

    fact[0], fact[1] = 1, 1
    inv[1] = 1
    finv[0], finv[1] = 1, 1

    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % mod
        inv[i] = mod - ((inv[mod % i] * (mod // i)) % mod)
        finv[i] = (finv[i - 1] * inv[i]) % mod

    return (fact[n] * finv[k] * finv[n-k]) % mod 

この方法をもとに、一度だけでなくなんども組み合わせの値を出力できるようにしたものは以下のようになります。

Comb.py

class Comb:

    def __init__(self, maxn, mod):
        self.fact = [0] * (maxn + 1)
        self.inv = [0] * (maxn + 1)
        self.finv = [0] * (maxn + 1)

        self.mod = mod

        self.fact[0], self.fact[1] = 1, 1
        self.inv[1] = 1
        self.finv[0], self.finv[1] = 1, 1

        for i in range(2, maxn + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = mod - ((self.inv[mod % i] * (mod // i)) % mod)
            self.finv[i] = (self.finv[i - 1] * self.inv[i]) % mod 

    def calc(self, n, k):
        return (self.fact[n] * self.finv[k] * self.finv[n-k]) % self.mod 

以上です。