【学习笔记】Lucas & ExtendedLucas

发表于 更新于

$\text{Lucas}$ 及其拓展定理用于处理 $\dbinom{n}{m} \bmod p$ 的问题，其中 $\text{Lucas}$ 定理处理 $p$ 是质数的情况，而其拓展定理能够处理 $p$ 不是质数的情况。

$\text{Lucas}$

若 $p$ 是质数，则对于 $\forall \quad 1 \leq m \leq n, \quad m,n \in \Z $ ，有：

本质就是把 $n$ 和 $m$ 表示为 $p$ 进制数，对 $p$ 进制下每一位分别计算组合数再乘起来，证明超过了这里的讨论范围，这里就省略了。

$\text{ExtendedLucas}$

$\text{ExtendedLucas}$ 能够处理模数不互质的情况，其实和 $\text{Lucas}$ 并没有多大关系 ，主要思想是对模数 $p$ 进行质因数分解，我们设模数 $p$ 能够被分解为如下形式：

我们记 $C = \dbinom{n}{m}$ ，我们只需求出

接着我们只需用 CRT 合并以下答案就会得到最后的结果。

现在我们要考虑的是如何求解 $C \bmod p^\alpha$ 的值。考虑到 $\dbinom{n}{m} = \frac{n!}{m!(n-m)!}$ ，所以我们只需要求解 $n! \bmod p^\alpha$ 即可。

不妨假设我们要求 $19! \bmod 3^2$ 。我们有

后半部分是阶乘，递归计算就可以了。

对于前半部分模 $3^2$ 有一个长度为 $6$ 的循环节（$1,2,4,5,7,8$），这样的话循环节整个进行统计，零头暴力即可。

$\text{Code}$

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// ---------- Lucas ------------------
inline int C(int n, int m, int p) {
	if (m > n) return 0;
	int ans = 1;
	for (int i = 1, a, b; i <= m; i++) {
		a = (n + 1 - i) % p;
		b = ModReverse(i % p, p);
		ans = ans * a % p * b % p;
	}
	return ans;
}
inline int Lucas(int n, int m, int p) {
	if (m == 0) return 1;
	return C(n % p, m % p, p) * C1(n / p, m / p, p) % p;
}

//------------- ExtendedLucas ---------------

inline int C(int n, int m, int p) {
	if (m > n) return 0;
	int ans = 1;
	for (int i = 1, a, b; i <= m; i++) {
		a = (n + 1 - i) % p;
		b = ModReverse(i % p, p);
		ans = ans * a % p * b % p;
	}
	return ans;
}
inline int C1(int n, int m, int p) {
	if (m == 0) return 1;
	return C(n % p, m % p, p) * C1(n / p, m / p, p) % p;
}
inline int calc(int n, int p) {
	int ans = 0;
	for (int i = n; i; i /= p) ans += i / p;
	return ans;
}
inline int fact(int n, int p, int t) {
	if (!n) return 1;
	int x = ModularPow(p, t), y = n / x, tmp = 1;
	for (int i = 1; i <= x; i++) 
		if (i % p) (tmp *= i) %= x;
	int ans = ModularPow(tmp, y, x);
	for (int i = y * x + 1; i <= n; i++)
		if (i % p) (ans *= i) %= x;
	return ans * fact(n / p, p, t) % x;
}
inline int C2(int n, int m, int p, int t) {
	int x = ModularPow(p, t);
	int ans = ModularPow(p, calc(n, p) - calc(m, p) - calc(n - m, p), x);
	int a = fact(n, p, t), b = fact(m, p, t), c = fact(n - m, p, t);
	ans = ans * a % x * ModReverse(b, x) % x * ModReverse(c, x) % x;
	return ans;
}
inline int ExtendedLucas(int n, int m, int p) {
	int cnt = 0;
	for (int i = 2; i * i <= p; i++) 
		if (p % i == 0) {
			int t = 0;
			while (p % i == 0) t++, p /= i;
			M[++cnt] = ModularPow(i, t);
			A[cnt] = t == 1 ? C1(n, m, i) : C2(n, m, i, t);
		}
	if (p > 1) M[++cnt] = p, A[cnt] = C1(n, m, p);
	return CRT(cnt); 
}