二項係数をmod表示する（中級編）【競技プログラミング】

# はじめに
- [初級編](https://qiita.com/kei_tnk/items/38bdf13cd92a176a9a8d)では、nが10000程度のケースまでしか対応できなかったので、10^7程度まで対応できるような実装を紹介します。
- ただし、ここから先は、modについて多少の知識が必要となります。具体的には、(mod M)における逆元を使用します。
- だから、この投稿は、ほぼ、(mod M)の逆元の話になるよ。

# (mod M)における逆元について
- 例えば、整数aに対する「aの逆元」を考えます。$a^{-1}$と書き、ax ≡ 1 (mod M) を満たすxの解です。
- 詳細は、[過去の投稿](https://qiita.com/kei_tnk/items/4a643b2f47d2aa919a1b#%E6%9C%89%E7%90%86%E6%95%B0ba%E3%82%92mod-998244353%E3%81%A7%E5%87%BA%E5%8A%9B%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E8%80%83%E5%AF%9F)を参考して欲しいけど、(<INS>mod 10</INS>)における逆元の具体的なイメージを書けば、
    - $1^{-1}$ ≡ 1 、言うまでもなく、全てのmに対して、1×1 ≡ 1 (mod m)となる。
    - $2^{-1}$ は存在しない。法10と2は素でないため、2x ≡ 1 を満たす解xは存在しない。感覚的にも、2にどんな数を乗じても、下一桁が1になることがないと分かるよね。
    - $3^{-1}$ ≡ 7 、これは 3×7=21 より分かる。
    - $4^{-1},5^{-1},6^{-1}$ は存在しない。
    - $7^{-1}$ ≡ 3 、これは 7×3=21 より分かる。
    - $8^{-1}$　は存在しない。
    - $9^{-1}$ ≡ 9 、これは 9×9=81 より分かる。
    - $10^{-1}$　は存在しない。
    - $11^{-1}$ ≡ 1 、これは 11×1=11 より分かる。

# どうして逆元で解決できるの？
- 初級編で書いた[脊髄反射で書いたような下記コード](https://qiita.com/kei_tnk/items/38bdf13cd92a176a9a8d#%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0%E3%81%AE%E7%AE%97%E5%87%BA%E6%96%B9%E6%B3%95%E8%84%8A%E9%AB%84%E5%8F%8D%E5%B0%84%E6%96%B9%E5%BC%8F)では、②部分で割り算が登場したので、mod化出来なかったね。
```swift
func comb(_ a:Int,_ b:Int)->Int{

    var c = a+b
    var a = a
    var b = b

    var ans = 1
    while c>1 { ans *= c ; c-=1 } // ①
    while a>1 { ans /= a ; a-=1 } // ②
    while b>1 { ans /= b ; b-=1 }
    
    return ans
}
```
- だけど、例えば(mod m)におけるaの逆数をinvMOD(a,m)とする関数invMODを用意できれば、②は`while a>1 { ans *= invMOD(a,m) ; a-=1 } `と書き換えることが出来るため、mod化が楽勝で出来るようになるね。
- そうすれば、高速化も多少は期待できるかな？まぁ、invMOD関数自体の計算量が重いと駄目だけどね。

# 逆元を算出する方法
- まず、[ベズーの等式](https://ja.wikipedia.org/wiki/%E3%83%99%E3%82%BA%E3%83%BC%E3%81%AE%E7%AD%89%E5%BC%8F)を紹介します。
:::note info
__ベズーの等式__
a と b を 0 でない整数とし、gcd(a,b) をそれらの最大公約数とする。このとき、以下の等式を成立させる整数 x と y が存在する。
```math
    ax + by = gcd(a,b)
```
※gcd:最大公約数(greatest common divisor)
:::
- つぎに、次の等式を紹介します。
:::note info
__ベズーの等式「っぽい見た目の」等式__
```math
\displaylines{
    n･n^{-1} + mk ≡ 1 \pmod m
}
```
※ nとmは素 ( ∵素でないと、nの逆元が存在しない)
※ $n･n^{-1}≡1$より、上記等式は任意のkについて成立する。
:::
- ここで、互いに素なnとmについて、ベズーの等式を当てはめると、gcd(n,m)=1より以下のことが言える。
    - `nx+my = 1`を成立させるx,yが存在する。
- よって、上記により求めた(x,y)を$(n^{-1},k)$と考えることが出来る。
- このように、$n^{-1}(=x)$を求める事ができます。
- なお、(a,b)より(x,y)を求めるコードは以下のとおりです。コードの解説は、[こちら](https://qiita.com/kei_tnk/items/4a643b2f47d2aa919a1b#%E3%81%8A%E3%81%BE%E3%81%91%E3%83%99%E3%82%BA%E3%83%BC%E3%81%AE%E7%AD%89%E5%BC%8F%E3%82%92%E6%BA%80%E3%81%9F%E3%81%99xy%E3%82%92%E7%AE%97%E5%87%BA%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0exgcdab)。
```swift
func exGCD(_ a:Int,_ b:Int)->(Int,Int){
    if (b == 0) {return (1,0)}
    let temp = exGCD(b,a % b)
    let q = a / b
    return (temp.1 , temp.0 - q * temp.1)
}

let a = 32
let b = 20
let ans = exGCD(a,b)

print( ans.0, ans.1, a*ans.0 + b*ans.1 ) // 2 -3 4
```
- このexGCDを利用して、逆元を求めるコードは、以下のとおり。
```swift
func invMOD(_ n:Int,_ mod:Int)->Int{
    var inv = exGCD(n,mod).0
    if inv < 0 {inv += mod}
    return inv    
}
```

# 脊髄反射コードに逆元を導入してmod化する
- もう、大した事は残ってないよ。
```swift
func comb(_ a:Int,_ b:Int)->Int{

    let mod = 1000000007

    var c = a+b
    var a = a
    var b = b

    var ans = 1
    while c>1 { ans = ans * c % mod ; c-=1 } // ①
    while a>1 { ans = ans * invMOD(a,mod) % mod ; a-=1 } // ②
    while b>1 { ans = ans * invMOD(b,mod) % mod ; b-=1 }
    
    return ans
}

func invMOD(_ n:Int,_ mod:Int)->Int{
    var inv = exGCD(n,mod).0
    if inv < 0 {inv += mod}
    return inv    
}

func exGCD(_ a:Int,_ b:Int)->(Int,Int){
    if (b == 0) {return (1,0)}
    let temp = exGCD(b,a % b)
    let q = a / b
    return (temp.1 , temp.0 - q * temp.1)
}

print(comb(10_000_000,10_000_000)) // 486682686
```
- 上記のとおり、$10^7$のオーダーの計算は出来ました。ちなみに$2×10^7$にしたらpaizaではtimeoutでした。

# おわりに
- ほとんど、[過去の投稿](https://qiita.com/kei_tnk/items/4a643b2f47d2aa919a1b)を再構成しただけだったね。
- でもこれで、桁が大きい場合の計算が出来るようになったよ！