In programming contests, when the answer is very large, we often have the problem of finding the remainder divided by a prime number. I learned how to think about such a problem, so I will summarize it. The sample code is basically Python 2.7. Reference: TopCoder Trends and Countermeasures 4 (C ++ Edition: Enumeration)

What should I do?

You just have to ask for too much each time you perform an operation.

In the case of addition

After adding, you can ask for too much.

mod = 1000000007

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

In the case of subtraction

In the case of Python, you can just pull it without thinking and then ask too much. If you have a language that requires too much negative value, you don't have to be careful.

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

When I tried it with C, it became a negative value. In this case, it seems better to add 1000000007 to ʻaand then subtractb`.

#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
}

The compiler used:

$ 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

In the case of multiplication

Multiply each other too much and take more.

mod = 1000000007

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

In the case of division

Suddenly, Fermat's Little Theorem comes out and I'm scared. Somehow it seems difficult. I'm not sure if it's division for the time being, so I'd like to fix it to multiplication.

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

That's what it is. Therefore, I want to find the inverse element of b in the world too much. Then we use Fermat's little theorem to find the inverse element. As for the process, if you look at the reference page, the result seems to be b to the 1000000005th power. In other words, in division, the following calculation should be done.

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

This time, we have to do a difficult calculation of b to the power of 1000000005, but we can use the dichotomous power method for this. First find the square, use it to find the 4th power, then use it to find the 8th power, and so on, it's much faster than multiplying b by 1000000005 times. Therefore, it is a story.

To summarize the above, the division is as follows.

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

It looks good, but it's not intuitive ...

I'll try to solve some problem

I tried it. This is a problem of combination calculation. AtCoder Beginner Contest 042: D --Iroha properly square

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

In the combination calculation, the factorial is used for division, so find the inverse element of the factorial that seems to be necessary in advance. At that time, if you calculate using the following, it seems to be fast because you do not have to calculate 1000000005 many times.

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

After that, I could do it by adding % mod properly.

in conclusion

To be honest, it doesn't look right, but I think it's probably done because I got AC. Until now, I couldn't get into the code because I was afraid of Fermat's little theorem, so I feel like I was able to move forward a little.

[PYTHON] Problem study memo to ask for too much divided by 1000000007