1000000007で割ったあまりを求める問題勉強メモ

プログラミングコンテストで、答えが非常に大きくなる場合に、素数で割ったあまりを求めよ、という問題がよく出ます。
そんな問題の考え方を勉強したのでまとめてみます。
サンプルのコードは基本的にPython2.7です。
参考: [TopCoder の傾向と対策４（Ｃ＋＋編：数え上げ）](http://nagoyacoder.web.fc2.com/topcoder/topcoder_cpp4.html)

# 何をすればいいの？
演算のたびに、都度あまりを求めていけばいいです。

## 足し算の場合
足した後、あまりを求めればいいです。

```py
mod = 1000000007

def add(a, b):
    return (a + b) % mod
```

## 引き算の場合
Pythonの場合は何も考えずに引いた後、あまりを求めればいいです。
マイナス値のあまりが求められる言語なら、特に気をつけることはありません。

```py
mod = 1000000007

def sub(a, b):
    return (a + mod - b) % mod

def sub_(a, b):
    return (a - b) % mod

print sub(1, 2) # => 1000000006
print sub_(1, 2) # => 1000000006
```

試しにCでやってみたら、マイナスの値になりました。
この場合は、`a`に1000000007を足してから`b`を引くのが良さそうです。

```c
#include <stdio.h>

int mod = 1000000007;

int sub(a, b) {
  return (a + mod - b) % mod;
}

int sub_(a, b) {
  return (a - b) % mod;
}

int main(void){
  printf("%d\n", sub(1, 2)); // => 1000000006
  printf("%d\n", sub_(1, 2)); // => -1
}
```

コンパイラは以下を使いました。

```
$ gcc -v
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin16.0.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
```

## 掛け算の場合
あまり同士を掛けて、さらにあまりをとります。

```py
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
```

## 割り算の場合
突然フェルマーの小定理とか出てきてビビります。なんか難しそう。
とりあえず割り算だとよくわからないので、掛け算に直したいみたいです。

```math
a \div b = a \times b^{-1}
```

こういうことですね。そこで、あまりの世界における`b`の逆元が求めたいと。
そして、その逆元を求めるのにフェルマーの小定理を使います。
過程は参考のページを見てもらうとして、結果は`b`の1000000005乗みたいです。
つまり、割り算では以下の計算をすればいいわけです。

```math
a \div b = a \times b^{1000000005} (mod 1000000007)
```

今度は`b`の1000000005乗という大変な計算をしなければいけないわけですが、これには二分累乗法が使えます。
まず2乗を求めて、それを使って4乗を求めて、さらにそれを使って8乗を求めて、、、とやっていけば、`b`を1000000005回掛けるより、ずっと速く求められますよって話です。

以上をまとめると、割り算は以下のようになります。

```py
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

print div(6, 3) # => 2
print div(10, 2) # => 5
print div(3000000000, 2) # => 499999993
print div(45000000000, 5) # => 999999944
print div(4000000000, 2000000000) # => 2
print div(45000000000, 5000000000) # => 9
```

良さそうだけど、直感的じゃないよなあ・・・

# せっかくなので何か問題を解いてみる
やってみました。組合せ計算をする問題です。
[AtCoder Beginner Contest 042: D - いろはちゃんとマス目](http://abc042.contest.atcoder.jp/tasks/arc058_b)

```py
mod = 1000000007
H, W, A, B = map(int, raw_input().split())

factorial = [1]
for n in xrange(1, H+W):
    factorial.append(factorial[n-1]*n%mod)

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

inverseFactorial = [0] * (H+W)
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in xrange(H+W-2, -1, -1):
    inverseFactorial[n] = inverseFactorial[n+1] * (n+1) % mod

def combi(n, m):
    return factorial[n] * inverseFactorial[m] * inverseFactorial[n-m] % mod

sum = 0
for i in xrange(B+1, W+1):
    sum = (sum + combi(H-A-1+i-1, i-1) * combi(A-1+W-i, W-i)) % mod
print sum
```

組合せ計算では階乗で割り算をすることになるので、予め必要そうな階乗の逆元を求めておきます。
そのときに以下を利用して計算すると、何度も1000000005乗の計算をしなくて済むので速いらしいです。

```math
n!^{-1} = (n+1)!^{-1} \times (n+1)
```

あとは、適宜`% mod`をちゃんとつけていけばできました。

# おわりに
正直イマイチしっくり来ていないですが、ACとれたので多分できているんだと思います。
今まではフェルマーの小定理にビビってコードに落とせなかったので、少しは前進できた気がします。