It is a commentary of D -Kight of AtCoder Beginner Contest yesterday (November 16, 2019). Mainly, I will write about how to calculate $ nCk $ $ \ pmod {10 ^ 9 + 7} $.
The $ X $, $ Y $ constraints in question, ・ $ 1 \ leqq X \ leqq 10 ^ 6 $ ・ $ 1 \ leqq Y \ leqq 10 ^ 6 $ Therefore, it is necessary to understand that DP, BFS, and DFS will be TLE. (Everything will be on the order of O (NM).)
If the above algorithm doesn't work, something needs to be done, so I came up with the idea that appears in Explanation. Then all you have to do is ask for $ nCk $ $ \ pmod {10 ^ 9 + 7} $.
What we need to find this time is that $ nCk = \ frac {n!} {K! (N-k)!} $ Divided by $ 10 ^ 9 + 7 $.
There are ** 4 ** points (confusing points) to find, so let's look at them in order.
This is the basis of mod calculation. It will cause an overflow, so take the remainder each time you stack. In the case of this formula
I know that I take $ mod $ $ 10 ^ 9 + 7 $ every time I multiply, but $ \ frac {1} {n-k-1} $ is a real division, so how should I calculate it? This is Kenchon's article,
Is easy to understand. In ** "3. Division a ÷ b" **, ** What is division in the world of mod p ** is described in detail.
If you write only the conclusion, In $ \ mod {p} $, the number that becomes $ 1 $ when multiplied by $ b $ is expressed as $ b ^ {-1} $. $ a \div b \equiv a \times b^{-1} \pmod{p}$ It will be. In other words, finding $ b ^ {-1} $ (multiplying it by a) is the division of the mod world. $ b ^ {-1} $ is called the ** inverse element ** of $ b $ in mod $ p $.
Then, how should we find the inverse element that appeared in II? This is also Kenchon's article,
The detailed explanation is written in. Personally, the explanation of "** 1-5. Another method of deriving the inverse recurrence formula **" was particularly easy to understand.
If you write only the conclusion here,
#inv is 1 ~(b-1)^-A list of inverse elements up to 1
inv[b] = - inv[MOD % b] * (MOD // i) % MOD
By the way, in Kenchon's implementation example, it is as follows, but it is the same because it is just adding MOD to the right side to make it a positive number.
inv[b] = MOD - inv[MOD % b] * (MOD // i) % MOD
Example) ・ $ 3 \ pmod {11} \ equiv 3 + 11 = 14 $ ・ $ -3 \ pmod {11} \ equiv -3 + 11 = 8 $
If you understand the above I to III, it will be a little more. What we want to find is $ \ pmod {p} $ in the following formula, where $ p = 10 ^ 9 + 7 $.
To find this
(1) List of factorial mods from $ 1 to n $
[
(2) Inverse factorial list
[
If you have it, you will find it easy to find.
(1) is
Regarding (2),
If you have all three, you can calculate $ nCk $ in the order of $ O (1) $.
The following is an example of the answer to this question.
def cmb(n, k, mod, fac, ifac):
"""
Calculate nCk
"""
k = min(k, n-k)
return fac[n] * ifac[k] * ifac[n-k] % mod
def make_tables(mod, n):
"""
Create a factorial table and an inverse factorial table
"""
fac = [1, 1] #Factorial table ...(1)
ifac = [1, 1] #Inverse factorial table ...(2)
inverse = [0, 1] #Inverse element table ...(3)
for i in range(2, n+1):
fac.append((fac[-1] * i) % mod)
inverse.append((-inverse[mod % i] * (mod//i)) % mod)
ifac.append((ifac[-1] * inverse[-1]) % mod)
return fac, ifac
X, Y = map(int, input().split())
#Later, n,To keep the size of m constant
if X > Y:
X, Y = Y, X
dist = X + Y
if dist % 3 != 0:
print(0)
else:
# (+1,+2)The number of movements of n,(+2,+1)Let m be the number of movements of)
# total = n + m
#The following formula is 2n+ m = X, n + 2m =The result of solving the simultaneous equations of Y
total = int((X+Y) / 3)
n = X - total
# n <0 or m<If it is 0, it cannot be reached
# Y >Because it is X, m> n
# n < 0 → 2X - Y < 0
if Y > 2*X:
print(0)
else:
MOD = 10**9 + 7
fac, ifac = make_tables(MOD, total)
ans = cmb(total, n, MOD, fac, ifac)
print(ans)
This time, the number to divide is $ 10 ^ 9 + 7 $, so I could calculate it without any problem, but it seems that not any number is fine. The relationship between the number of divisions $ p $ and $ nCr $ is
Is required.
Recommended Posts