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

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

何をすればいいの？

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

足し算の場合

足した後、あまりを求めればいいです。

mod = 1000000007

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

引き算の場合

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

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を引くのが良さそうです。

#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

掛け算の場合

あまり同士を掛けて、さらにあまりをとります。

mod = 1000000007

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

割り算の場合

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

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

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

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

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

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

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 - いろはちゃんとマス目

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乗の計算をしなくて済むので速いらしいです。

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

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

おわりに

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