Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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

何をすればいいの?

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

足し算の場合

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

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とれたので多分できているんだと思います。
今まではフェルマーの小定理にビビってコードに落とせなかったので、少しは前進できた気がします。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした