【算法笔记】大整数取余小结 & Faberge easter eggs crush test

本文已参加「新人创造礼」活动，一同敞开掘金创造之路

背景

很多OJ标题会涉及对一个大质数取余数。

基础知识

• Lucas定理

  

• 费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）
• 快速幂：zhuanlan.zhihu.com/p/95902286

常见题型

1. 幂次取余：即核算a^n mod p。用快速幂算。
2. 组合数取余：即核算C(n, m) mod p. 使用如下战略：

• 在n >= p的情况下，先使用Lucas定理，将求余的对象转成多个组合数的乘积。
• 在转化到n, m < p之后，考虑到C(n, m) = n! / m! / (n-m)!，而根据费马小定理，m! ^ (p-1) mod p == 1, (n-m)! ^ (p-1) == 1，三者相乘可得，C(n, m)和n!*(m!(n-m)!) ^ (p-2)mod p同余。因而，核算n! mod p和(m!(n-m)!) ^ (p-2) mod p即可。后者能够用快速幂求，且m!(n-m)! mod p能够在求n! mod p的过程中求出。

例题

CodeWars – Faberge easter eggs crush test

首先列个DP的递推式，然后核算，发现这道题的中心是求length(n, m) = C(m, 1) + ... + C(m, n). 对大素数MOD的模。（好吧，实际上看样例就能猜出来通项公式。）

Step 1.

forall n < MOD, C(m, n) = C(m//MOD, n//MOD) * C(m%MOD, n%MOD) = C(m//MOD, 0) * C(m%MOD, n) = C(m%MOD, n). （同模MOD含义下的相等）

注意到标题条件，标题中的n < MOD必定，所以在m较大的时候，先将其转化为m对MOD的余数，即length(n, m) = length(n, m % MOD).

Step 2.

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

考虑到这一点，length(n, m) = length(min(n, m), m).

Step 3.

C(m, 1) = m C(m, i+1) = C(m, i) * (m-i) / (i+1) = C(m, i) * (m-i) * (i+1) ^ (MOD-2) （同模MOD含义下的相等）

考虑到这一点，在核算每个组合数对大素数的余数时，咱们能够迭代地核算。 别的，考虑到评测体系会运行多个测试样例，为了功率，咱们能够先把1 ^ (MOD-2), 2 ^ (MOD-2), ...的结果存储下来，防止在使用时进行重复核算。

执行完这三步就能通过这道题。代码不放了。