プログラミングコンテストで、答えが非常に大きくなる場合に、素数で割ったあまりを求めよ、という問題がよく出ます。
そんな問題の考え方を勉強したのでまとめてみます。
サンプルのコードは基本的に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とれたので多分できているんだと思います。
今まではフェルマーの小定理にビビってコードに落とせなかったので、少しは前進できた気がします。