Background

Nice to meet you. I am a beginner who started working on competitive professionals last week.

Yesterday, there was a contest called Atcoder Grand Contest, which is one of the most difficult contests in Atcoder, and I participated for the first time.

Yesterday's one was the most difficult one, and depending on the speed, it was enough to get an orange performance with 2 finishes. I was able to solve only one question, but I was also surprised at the difficulty of the first question (too different from ABC)

When I read the explanation of 2nd question, the theorem ** Lucas's theorem ** came out. (If you are interested, please read the problem statement as well) I was surprised when it came out like common sense lol

When I googled with * "Lucas's Theorem Competition Pro" *, I hit it, so I thought it should be remembered, and I decided to explain and implement it until now. (Implemented in python)

ps.) Is it a common sense theorem in the professional competition area? I would appreciate it if you could tell me.

What is Lucas's theorem?

p: prime number m, n: non-negative integer C (n, k): = (number when selecting k out of n) When

  C(m,n) \equiv \prod_{i=0}^l C(m_i, n_i) \ \ \ \  (mod\ p) \\

However,

m_lm_{l−1}⋯m_1m_0 := (p-adic display of m)\\
n_ln_{l−1}⋯n_1n_0 := (n p-adic display)

And.

What do you want to do after all

When I summarize it in my own way ** "Theorem to enjoy when finding the remainder of C (n, k)" ** I interpreted it like this.

Example in this case

In the question of this contest, since the information required the evenness of C (n, k) for all the input numbers, Lucas's theorem is used to find it. (P = 2)

For example, when finding the evenness of C (7,2), (n = 5, k = 2)

7\ → 111\\
2\ → 010

First convert n and k to binary, then Find C (n, k) for each digit and multiply by the found C (n, k).

C(1,0)*C(1,1)*C(1,0) = 1*1*1 = 1

Therefore, the remainder of dividing C (7,2) by 2 can be derived as 1, and it can be seen that it is an odd number.

Implementation

The implementation itself is not so difficult, but it is troublesome to do it during the contest, so I implemented it so that it can be used in the future. (Please point out any mistakes)

from scipy.special import comb

#Function that converts x to n-ary notation
def n_ary(x, n):
	nums = '0123456789ABCDEF'
	result = ''
	while(1):
		result = nums[int(x % n)] + result
		x = x // n
		if x==0:
			break
	return result

# C(n,k)A function that returns the remainder of dividing by p
def lucas(n, k, p):
	#Notation of n and k in p-adic
	n_p = n_ary(n, p)
	k_p = n_ary(k, p)
	# n_p and k_Align the digits of p(Fill the left side with 0)
	k_p = k_p.zfill(len(n_p))

	result = 1
	for n_i, k_i in zip(n_p, k_p):
		result *= comb(int(n_i), int(k_i), exact=True)
	return result

Summary

When I finished the contest and saw the answer, I felt "I can't think of it." However, when I watched the explanation video after that,

――If you are doing it to some extent, you know it ~ ――It's a common method ~

The commentator was saying a phrase like this, and I was informed of my lack of knowledge. There may be a problem with the power of Hirameki, but before that I realized that I lacked knowledge, so I decided to worry about Hirameki after I had the knowledge. (In this case, when Pascal's triangle-like thing came out, I had to think of it as a binomial coefficient entanglement)

In the next Grand Contest, I will reinforce my knowledge so that I can complete 2.