卢卡斯定理
Lucas 定理¶
Lucas 定理用于求解大组合数取模的问题,其中模数必须为素数。正常的组合数运算可以通过递推公式求解(详见 排列组合),但当问题规模很大,而模数是一个不大的质数的时候,就不能简单地通过递推求解来得到答案,需要用到 Lucas 定理。
求解方式¶
Lucas 定理内容如下:对于质数 p,有
观察上述表达式,可知 n\bmod p 和 m\bmod p 一定是小于 p 的数,可以直接求解,\displaystyle\binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor} 可以继续用 Lucas 定理求解。这也就要求 p 的范围不能够太大,一般在 10^5 左右。边界条件:当 m=0 的时候,返回 1。
时间复杂度为 O(f(p) + g(n)\log n),其中 f(n) 为预处理组合数的复杂度,g(n) 为单次求组合数的复杂度。
代码实现
1 2 3 4 5 |
|
1 2 3 4 5 |
|
Lucas 定理的证明¶
考虑 \displaystyle\binom{p}{n} \bmod p 的取值,注意到 \displaystyle\binom{p}{n} = \frac{p!}{n!(p-n)!},分子的质因子分解中 p 次项恰为 1,因此只有当 n = 0 或 n = p 的时候 n!(p-n)! 的质因子分解中含有 p,因此 \displaystyle\binom{p}{n} \bmod p = [n = 0 \vee n = p]。进而我们可以得出
注意过程中没有用到费马小定理,因此这一推导不仅适用于整数,亦适用于多项式。因此我们可以考虑二项式 f^p(x)=(ax^n + bx^m)^p \bmod p 的结果
考虑二项式 (1+x)^n \bmod p,那么 \displaystyle\binom n m 就是求其在 x^m 次项的取值。使用上述引理,我们可以得到
注意前者只有在 p 的倍数位置才有取值,而后者最高次项为 n\bmod p \le p-1,因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值,即在前者部分取 p 的倍数次项,后者部分取剩余项,即 \displaystyle\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p。
素数在阶乘中的幂次¶
Legengre 在 1808 年指出 n! 中含有的素数 p 的幂次为 \sum_{j\geq 1}\lfloor n/p^j\rfloor。
证明:将 n! 记为 1\times 2\times \cdots \times p\times \cdots \times 2p\times \cdots \times \lfloor n/p\rfloor p\times \cdots \times n 那么其中 p 的倍数有 p\times 2p\times \cdots \times \lfloor n/p\rfloor p=p^{\lfloor n/p\rfloor }\lfloor n/p\rfloor ! 然后在 \lfloor n/p\rfloor ! 中继续寻找 p 的倍数即可,这是一个递归的过程。为了方便记 \nu(n!)=\sum_{j\geq 1}\lfloor n/p^j\rfloor。
另一种其他地方比较常见的公式,用到了 p 进制下各位数字和:
v_p(n!)=\frac{n-S_p(n)}{p-1}
与等比数列求和公式很相似。由于涉及各位数字和,利用数学归纳法可以轻松证明。
特别地,阶乘中 2 的幂次是:
v_2(n!)=n-S_2(n)
素数在组合数中的幂次¶
组合数对一个数取模的结果,往往构成分形结构,例如谢尔宾斯基三角形就可以通过组合数模 2 得到。
v_p(C_m^n)=\frac{S_p(n)+S_p(m-n)-S_p(m)}{p-1}
如果仔细分析,p 是否整除组合数其实和上下标在 p 进制下减法是否需要借位有关。这就有了 Kummer 定理。
Kummer 定理:p 在组合数 C_m^n 中的幂次,恰好是 p 进制下 m 减掉 n 需要借位的次数。
特别地,组合数中 2 的幂次是:
v_2(C_m^n)=S_2(n)+S_2(m-n)-S_2(m)
exLucas 定理¶
Lucas 定理中对于模数 p 要求必须为素数,那么对于 p 不是素数的情况,就需要用到 exLucas 定理。
求解思路¶
第一部分:中国剩余定理¶
要求计算二项式系数 \binom{n}{m}\bmod M,其中 M 可能为合数。
考虑利用 中国剩余定理 合并答案,这种情况下我们只需求出 \binom{n}{m}\bmod p^q 的值即可(其中 p 为素数且 q 为正整数)。
根据 唯一分解定理,将 p 质因数分解:
对于任意 i,j,有 {q_i}^{\alpha_i} 与 {q_j}^{\alpha_j} 互质,所以可以构造如下 r 个同余方程:
我们发现,在求出 a_i 后,就可以用中国剩余定理求解出 \displaystyle\binom{n}{m}。
第二部分:移除分子分母中的素数¶
根据同余的定义,\displaystyle a_i=\binom{n}{m}\bmod {q_i}^{\alpha_i},问题转化成,求 \displaystyle \binom{n}{m} \bmod q^k(q 为质数)的值。
根据组合数定义 \displaystyle \binom{n}{m} = \frac{n!}{m! (n-m)!},\displaystyle \binom{n}{m} \bmod q^k = \frac{n!}{m! (n-m)!} \bmod q^k。
由于式子是在模 q^k 意义下,所以分母要算乘法逆元。
同余方程 ax \equiv 1 \pmod p(即乘法逆元)有解 的充要条件为 \gcd(a,p)=1(裴蜀定理),
然而 无法保证有解,发现无法直接求 \operatorname{inv}_{m!} 和 \operatorname{inv}_{(n-m)!},
所以将原式转化为:
x 表示 n! 中包含多少个 q 因子,y, z 同理。
第三部分:Wilson 定理的推论¶
问题转化成,求形如:
的值。这时可以利用 Wilson 定理的推论。如果难以理解,可以看看下面的解释。
一个示例:22! mod 9¶
先考虑 n! \bmod q^k,
比如 n=22, q=3, k=2 时:
22!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12
\times 13\times 14\times 15\times 16\times 17\times 18\times 19\times20\times21\times22
将其中所有 q 的倍数提取,得到:
22!=3^7 \times (1\times 2\times 3\times 4\times 5\times 6\times 7)\times(1\times 2\times 4\times 5\times 7\times 8\times 10 \times 11\times 13\times 14\times 16\times 17\times 19 \times 20 \times 22 )
可以看到,式子分为三个整式的乘积:
-
是 3 的幂,次数是 \lfloor\frac{n}{q}\rfloor;
-
是 7!,即 \lfloor\frac{n}{q}\rfloor!,由于阶乘中仍然可能有 q 的倍数,考虑递归求解;
-
是 n! 中与 q 互质的部分的乘积,具有如下性质:
1\times 2\times 4\times 5\times 7\times 8\equiv10 \times 11\times 13\times 14\times 16\times 17 \pmod{3^2},
即:\displaystyle \prod_{i,(i,q)=1}^{q^k}i\equiv\prod_{i,(i,q)=1}^{q^k}(i+tq^k) \pmod{q^k}(t 是任意正整数)。
\displaystyle \prod_{i,(i,q)=1}^{q^k}i 一共循环了 \displaystyle \lfloor\frac{n}{q^k}\rfloor 次,暴力求出 \displaystyle \prod_{i,(i,q)=1}^{q^k}i,然后用快速幂求 \displaystyle \lfloor\frac{n}{q^k}\rfloor 次幂。
最后要乘上 \displaystyle \prod_{i,(i,q)=1}^{n \bmod q^k}i,即 19\times 20\times 22,显然长度小于 q^k,暴力乘上去。
上述三部分乘积为 n!。最终要求的是 \frac{n!}{q^x}\bmod{q^k}。
所以有:
于是:
\displaystyle \left(\left\lfloor\frac{n}{q}\right\rfloor\right)! 同样是一个数的阶乘,所以也可以分为上述三个部分,于是可以递归求解。
等式的右边两项不含素数 q。事实上,如果直接把 n 的阶乘中所有 q 的幂都拿出来,等式右边的阶乘也照做,这个等式可以直接写成:
式中的 x 和 x' 都表示把分子中所有的素数 q 都拿出来。改写成这样,每一项就完全不含 q 了。
递归的结果,三个部分中,左边部分随着递归结束而自然消失,中间部分可以利用 Wilson 定理的推论 0,右边部分就是推论 2 中的 \prod_{j\geq 0}(N_j!)_p。
下面这种写法,拥有单次询问 O(p\log p) 的时间复杂度。其中 int inverse(int x)
函数返回 x 在模 p 意义下的逆元。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
若不考虑 excrt 的复杂度,通过预处理 \frac{n!}{n以内的p的所有倍数的乘积}\bmod{p},可以使时间复杂度优化至单次 O(p + \log p)。而如果 p 是固定的,我们在一开始就可以对 p 进行分解,并进行预处理,可以达到总复杂度 O(p + T\log p)。
习题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用