[AtCoder] How to find the binomial coefficient nCk mod.p [D --Knight]

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} $.

Way of thinking

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} $.

How to find and think about nCk

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.

Ⅰ. When calculating nCk, take the remainder for each multiplication

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 \frac{n!}{k!(n-k)!} = n \times (n-1) \times ... \times 1 \times (\frac{1}{k} \times \frac{1}{k-1} \times ... \frac{1}{1}) \times (\frac{1}{n-k} \times \frac{1}{n-k-1} \times ... \frac{1}{1}) However, when calculating each element $ n-1, \ frac {1} {n-k-1} $, it means that $ mod $ $ 10 ^ 9 + 7 $ is taken. However, the following question II arises here.

Ⅱ. What is division in mod p?

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 $.

Ⅲ. How to find the inverse element?

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, b^{-1} \pmod{p} To calculate $ b^{-1} \equiv -(p%b)^{-1} \times (p/b) \pmod{p} $ It can be said that it is to calculate the right side of.

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

Ⅳ. How to find nCk efficiently?

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 $.

\frac{n!}{k!(n-k)!} = n \times (n-1) \times ... \times 1 \times (\frac{1}{k} \times \frac{1}{k-1} \times ... \frac{1}{1}) \times (\frac{1}{n-k} \times \frac{1}{n-k-1} \times ... \frac{1}{1})

To find this

(1) List of factorial mods from $ 1 to n $  [1!\pmod{p}, 2!\pmod{p}, ..., n!\pmod{p}]

(2) Inverse factorial list  [\frac{1}{1!}\pmod{p}, \frac{1}{2!}\pmod{p}, ..., \frac{1}{n!}\pmod{p}]

If you have it, you will find it easy to find. (1) is n!\pmod{p} \equiv (n-1)!\pmod{p} \times n And so on, it can be easily calculated using the previous element.

Regarding (2), \frac{1}{n!}\pmod{p} \equiv \frac{1}{(n-1)!}\pmod{p} \times \frac{1}{n}(=n^{-1}) However, as we learned in III, to find $ n ^ {-1} $, we need a list of inverse elements from $ 0 $ to $ n-1 . Therefore, in addition to (1) and (2), (3) List of inverse elements  [\frac{1}{1}\pmod{p}$, \frac{1}{2}\pmod{p}, ..., \frac{1}{n}\pmod{p}]

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)

Remarks

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

[AtCoder] How to find the binomial coefficient nCk mod.p [D --Knight]
How to calculate the autocorrelation coefficient
How to find the area of the Voronoi diagram
How to find the correlation for categorical variables
How to find the coefficient of the trendline that passes through the vertices in Python
How to find the optimal number of clusters in k-means
How to find the scaling factor of a biorthogonal wavelet
How to use the generator
How to find Mahalanobis distance
How to use the decorator
How to increase the axis
How to start the program
How to find the memory address of a Pandas dataframe value
How to find if you don't know the Java installation directory
How to use the zip function
How to use the optparse module
[Python] How to derive nCk (ABC156-D)
How to read the SNLI dataset
How to get the Python version
[Python] How to import the library
How to overwrite the output to the console
How to use the ConfigParser module
How to find out the number of CPUs without using the sar command