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)
You just have to ask for too much each time you perform an operation.
After adding, you can ask for too much.
mod = 1000000007
def add(a, b):
return (a + b) % mod
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
Multiply each other too much and take more.
mod = 1000000007
def mul(a, b):
return ((a % mod) * (b % mod)) % mod
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 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.
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.
Recommended Posts