This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together

background

Many OJ problems involve taking the remainder of a large prime number.

Basic knowledge of

  • Lucas theorem

  • Fermat’s Little theorem: If P is a prime number and the integer A is not a multiple of P, then a^ (p-1) ≡1 (mod p)
  • Fast power: zhuanlan.zhihu.com/p/95902286

Common topic

  1. Power mod: that is, calculatea^n mod p. Use quick powers.
  2. Combination number mod: that is, calculationC(n, m) mod p. Use the following policies:
  • inn >= pIn the case of, Lucas theorem is first used to transform the remainder object into the product of multiple combination numbers.
  • In the transformation to then, m < pAnd then, let’s think aboutC(n, m) = n! / m! / (n-m)!And according to Fermat’s little theorem,m! ^ (p-1) mod p == 1, (n-m)! ^ (p-1) == 1When multiplied by the three,C(n, m)andn! *(m! (n-m)!) ^ (p-2)Mod p congruence. So, calculaten! mod pand(m! (n-m)!) ^ (p-2) mod pCan. The latter can be solved by quick exponentiation, andm! (n-m)! mod pIn on! mod pI’m going to figure out.

sample

CodeWars – Faberge easter eggs crush test

Length (n, m) = C(m, 1) +… length(n, m) = C(m, 1) +… + C(m, n). Modulo of large prime MOD. (Well, you can actually guess the general formula by looking at an example.)

Step 1.

Forall n < MOD, C (m, n) = C (m / / MOD, n / / MOD) * C (MOD) MOD, m % n % = C (m / / MOD, 0) * C (m % MOD, n) = C (m % MOD, n). (with the die MOD sense equal)

Note that n < MOD in the question is inevitable, so when M is large, it is first converted to the remainder of M to MOD, that is, length(n, m) = length(n, m % MOD).

Step 2.

when n > m, C(m, n) = 0.

With this in mind, length(n, m) = length(min(n, m), m).

Step 3.

M C (m, 1) = C (m, I + 1) = C (m, I) * (m – I)/(I + 1) = C (m, I) * (m – I) * (I + 1) ^ (2) MOD – (equal) with the die MOD sense

With this in mind, we can calculate iteratively when calculating the remainder of each combination over a large prime. In addition, considering that the evaluation system will run multiple test samples, for efficiency, we can first put 1 ^ (MOd-2), 2 ^ (mod-2),… The results are stored to prevent double calculation when used.

Do these three steps to pass the problem. The code is stuck.