抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

前言

本文主要介绍了 Lucas 定理及其扩展,并附以若干道相关习题。

公式可能偏多,但是只要静下心来慢慢读还剩可以读得懂的 qwq。

本文用到了的前置知识:

  • 简单的排列组合
  • 普及~提高的数论知识
  • 二项式定理
  • 简单的生成函数知识
  • 乘法逆元
  • 中国剩余定理(CRT)
  • 欧拉定理(可选,习题涉及)
  • 整除分块(习题涉及其思想)

普通 Lucas(模数为质数)

问题描述

\binom n m\bmod p

的值,其中 n m 可以很大, p 为一个不大的质数。

结论(Lucas 定理)

\binom n m \equiv \binom{\lfloor\frac n p\rfloor}{\lfloor\frac m p\rfloor}\cdot \binom{n\bmod p}{m\bmod p}\pmod p

体现在程序中就是: \binom{\lfloor\frac n p\rfloor}{\lfloor\frac m p\rfloor} 可以递归求解, \binom{n\bmod p}{m\bmod p} 可以直接算,时间复杂度为 O(f(p) + g(n)\log n) ,其中 f(p) 为预处理组合数的时间复杂度, g(n) 为单次询问组合数的时间复杂度。

证明

参考了 OI-Wiki 的证明并加以了自己的说明和补充。

引理

首先考虑

\binom p n \bmod p

的取值,注意到展开组合数之后其为如下形式:

\frac{p!}{n!(p-n)!}\bmod p

而显然,由于分子中 p! 是一定有质因子 p 的,所以只有当 n = 0\lor n = p 的时候(即 p! 能被消干净)整体的结果为 1 ,否则为 0 。即

\binom p n\bmod p = [n = 0\lor n = p]

进而我们可以得到

\begin{aligned} (a + b)^p&=\sum_{n = 0}^p\binom p na^nb^{p - n}\\ &\equiv \sum_{n= 0}^p[n = 0\lor n = p]a^np^{p - n}\\ &\equiv a^p + b^p\pmod p \end{aligned}

然后将其推广到二项式的情况,

\begin{aligned} (ax^n + bx^m)^p&\equiv a^px^{np} + b^px^{mp}\\ &\equiv ax^{np} + bx^{mp} \end{aligned}

即我们可以直接把指数 p 给提进来。

证明

考虑二项式 (1+x)^n x^m 处的系数模 p 的结果,不难发现其即为 \displaystyle\binom n m\bmod p 。利用上述引理,我们可以做出如下推导:

\begin{aligned} (1+x)^n&\equiv(1+x)^{p\lfloor n/p\rfloor}(1+x)^{n\bmod p}\\ &\equiv(1+x^p)^{\lfloor n/p\rfloor}(1+x)^{n\bmod p} \end{aligned}

我们将其看作两个多项式 (1+x^p)^{\lfloor n/p\rfloor} (1+x)^{n\bmod p} 的卷积,考虑这两个式子对 (1 + x)^n 产生的贡献:

  • (1+x^p)^{\lfloor n/p\rfloor} 展开后得到的项的次数均为 p 的倍数。
  • (1+x)^{n\bmod p} 展开后得到的项的次数最多为 p - 1

所以对 x^m 的系数仅有一种产生贡献的方案,考虑一下这个贡献怎么来的:就是 (1+x^p)^{\lfloor n/p\rfloor} 中取 p 的倍数次项,这部分的系数即 \displaystyle\binom{\lfloor\frac n p\rfloor}{\lfloor\frac m p\rfloor} ,然后在 (1+x)^{n\bmod p} 中取剩余的部分,这部分的系数即 \displaystyle\binom{n\bmod p}{m\bmod p}

所以我们得出结论

\binom n m \equiv \binom{\lfloor\frac n p\rfloor}{\lfloor\frac m p\rfloor}\cdot \binom{n\bmod p}{m\bmod p}\pmod p

代码实现

1
2
3
4
5
6
int lucas(int n, int m)
{
if (!m) return 1;
return 1ll * lucas(n / p, m / p) * C(n % p, m % p) % p;
}

写的时候注意边界 m = 0 即可,然后对于 \displaystyle\binom{\lfloor\frac n p\rfloor}{\lfloor\frac m p\rfloor} 用 Lucas 定理继续递归计算,而右边的 \displaystyle\binom{n\bmod p}{m\bmod p} 因为 p 较小,直接求即可。

总的实现:洛谷 P3807 【模板】卢卡斯定理

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
#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return x ? -s : s;
}

const int maxn = 3e5 + 5;
int n, m, p, fact[maxn];

int qpow(int base, int p, int mod)
{
int ret = 1;
for (; p; p >>= 1, base = 1ll * base * base % mod)
if (p & 1) ret = 1ll * ret * base % mod;
return ret;
}

int C(int n, int m)
{
if (m > n) return 0;
return 1ll * fact[n] * qpow(1ll * fact[m] * fact[n - m] % p, p - 2, p) % p;
}

int lucas(int n, int m)
{
if (!m) return 1;
return 1ll * lucas(n / p, m / p) * C(n % p, m % p) % p;
}

int main()
{
int T = read();
while (T--)
{
m = read(), n = read() + m, p = read();
fact[0] = 1;
FOR(i, 1, 3e5) fact[i] = 1ll * i * fact[i - 1] % p;
printf("%d\n", lucas(n, m));
}
return 0;
}

exLucas(模数不一定为质数)

继续之前,假定读者已熟练掌握乘法逆元和 CRT。

这个东西除了和 Lucas 定理长得像之外和 Lucas 就没有半毛钱关系了,而且比 Lucas 阴间 n 多倍

问题描述

\binom nm\bmod p

的值。其中 p 不一定为质数且 p 较小。

问题求解

参考了 OI-Wiki 并加以自己的说明和补充。

Part 1

使用唯一分解定理分解模数 p 得到:

p = \prod_{i = 1}^rq_i^{k_i}

然后由于 q_i^{k_i} q_j^{k_j} 两两互质,所以可以构造如下的同余方程组

\begin{cases}x\equiv\dbinom n m\pmod{q_1^{k_1}}\\x\equiv\dbinom n m\pmod{q_2^{k_2}}\\\quad\cdots\\x\equiv\dbinom n m\pmod{q_r^{k_r}}\end{cases}

然后用 CRT 合并解即可。

Part 2

现在的问题变成了求 \displaystyle\binom n m \bmod{q^k} q 为质数)的值。拆开组合数的式子,我们发现:

\binom n m \equiv \frac{n!}{m!(n - m)!}\pmod{q^k}

然而下面那个东西不一定能算模 q^k 意义下的乘法逆元,那么我们就把所有的 q 提出来:

\frac{\frac{n!}{q^x}}{\frac{m!}{q^y}\frac{(n - m)!}{q^z}}q^{x - y - z}\bmod q^k

其中 x 表示 n! 中质因子 q 的次数, y z 同理。这样子分数线下面的式子由于与 q^k 互质,就可以求逆元了。

Part 3

现在需要解决的就是求

f(n) \equiv \frac{n!}{q^x}\pmod{q^k}

的值。

先考虑 n!\bmod q^k 的值。以一个最常见的例子: n = 22 q = 3 k = 2 为例:

\begin{aligned} 22! = 1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12\\\times13\times14\times15\times16\times17\times18\times19\times20\times21\times22 \end{aligned}

把所有 q 的倍数提取出来,即为

\begin{aligned} 22! =& (3\times6\times9\times12\times15\times18\times21)\times1\times2\times4\times5\times7\\&\times8\times10\times11\times13\times14\times16\times17\times19\times20\times22\\ =&3^7\times(1\times2\times3\times4\times5\times6\times7)\times1\times2\times4\times5\times7\\&\times8\times10\times11\times13\times14\times16\times17\times19\times20\times22\\ \end{aligned}

注意一下这个分组

  • 3^7 即为 q^{\lfloor n/q\rfloor}

  • 还剩下一个 7! 即为 \lfloor n/q\rfloor! ,这一部分可以递归进行求解。

  • 最后剩下来的就是 n! 中与 q 互质的部分的乘积。可以发现

    1\times2\times4\times5\times7\times8\equiv10\times11\times13\times14\times16\times17\pmod{3^2}

    所以其相当于就是一个循环节,我们再重新写一下 22! 的展开:

    22! \equiv 3^7\times7!\times(1\times2\times4\times5\times7\times8)^2\times(19\times20\times22)\pmod{3^2}

    关于循环节,可以这样理解:

    \prod_{i,i\perp q}^{q^k}i\equiv\prod_{i,i\perp q}^{q^k}(i + tq^k)\pmod{q^k}

    其中 t\in\mathbb N^* 。这个循环节循环了 \displaystyle\left\lfloor\frac{n}{q^k}\right\rfloor 次,所以考虑暴力把 \displaystyle\prod_{i,i\perp q}^{q^k}i 求出来然后快速幂求一波 \displaystyle\left\lfloor\frac{n}{q^k}\right\rfloor 次幂。当然最后是需要乘上余项 \displaystyle\prod_{i,i\perp q}^{n\bmod q^k}i (对应上面的 19\times20\times22 ),暴力就可以了。

总结下来就是

n!\equiv q^{\lfloor n/q\rfloor}\cdot\left(\left\lfloor\frac n q\right\rfloor\right)!\cdot\left(\prod_{i, i\perp q}^{q^k}i\right)^{\lfloor n / q^k\rfloor}\cdot \left(\prod_{i, i\perp q}^{n\bmod q^k}i\right)\pmod{q^k}

而我们需要求的是 \displaystyle\frac{n!}{q^x}\bmod q^k

变形一下上面的式子得到

f(n)\equiv f\left(\left\lfloor\frac n q\right\rfloor\right)\cdot\left(\prod_{i, i\perp q}^{q^k}i\right)^{\lfloor n / q^k\rfloor}\cdot \left(\prod_{i, i\perp q}^{n\bmod q^k}i\right)\pmod{q^k}

(注意此时 n! 中的质因子 q 会在递归的过程中全部被消掉),此时我们就求得 f(n) 的值了。

这一部分的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
ll calc(ll n, ll q, ll qk)//传入的参数不再赘述
{
if (!n) return 1;//边界条件
ll ret = 1;
FOR(i, 1, qk)
if (i % q) ret = ret * i % qk;//处理循环节的部分
ret = qpow(ret, n / qk, qk);//给循环节进行快速幂
FOR(i, n / qk * qk + 1, n)
if (i % q) ret = ret * (i % qk) % qk;//暴力合并余项,注意这里一定要先取模再乘不然会去世
return ret * calc(n / q, q, qk) % qk;//递归继续求解
}

Part 4

那么回到刚才的问题:求

\frac{\frac{n!}{q^x}}{\frac{m!}{q^y}\frac{(n - m)!}{q^z}}q^{x - y - z}\bmod q^k

左边分数的分子可以求,分母由于必然与 q^k 互质是可以求逆元的,现在问题就是如何去求这个 q^{x - y - z}

不妨设 g(n) = x ,则由刚才的推导过程可以知道

g(n) = \left\lfloor\frac n q\right\rfloor + g\left(\left\lfloor\frac n q\right\rfloor\right)

(其实就是考虑当前求 n! q 的倍数产生的贡献和下面求 \lfloor n / q\rfloor! q 的倍数产生的贡献)

当然我们其实有一种更加简洁的去求 x - y - z 的方法:

1
2
3
4
5
ll cnt = 0;
for (ll i = n; i; i /= q) cnt += i / q;
for (ll i = m; i; i /= q) cnt -= i / q;
for (ll i = n - m; i; i /= q) cnt -= i / q;

这样做的道理其实也很简单,完全就是把递归式的 g(n) 换成了非递归式而已。

那么所有的问题就已经搞定了。

这一部分的代码如下:

1
2
3
4
5
6
7
8
9
ll multiLucas(ll n, ll m, ll q, ll qk)//求 \binom n m \pmod{q ^ k} 的值
{
int cnt = 0;
for (ll i = n; i; i /= q) cnt += i / q;
for (ll i = m; i; i /= q) cnt -= i / q;
for (ll i = n - m; i; i /= q) cnt -= i / q;
return qpow(q, cnt, qk) * calc(n, q, qk) % qk * inv(calc(m, q, qk), qk) % qk * inv(calc(n - m, q, qk), qk) % qk;
}

流程回顾

  1. 对于 p 分解质因数得到每个质因子 q^k

  2. 对于每个质因子,求出

    \binom n m\equiv \frac{f(n)}{f(m)f(n - m)}\cdot q^{g(n) - g(m) - g(n - m)}\pmod{q^k}

  3. 用 CRT 合并所有答案

代码实现

细节非常的繁冗,一定要注意关于取模/long long/是否爆范围之类的问题。

洛谷 P4720 【模板】扩展卢卡斯

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#define FOR(i, a, b) for (ll i = a; i <= b; ++i)
#define DEC(i, a, b) for (ll i = a; i >= b; --i)

typedef long long ll;

ll mod;

void exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
return;
}

inline ll inv(ll n, ll p)
{
ll x, y;
exgcd(n, p, x, y);
return (x + p) % p;
}

ll qpow(ll base, ll p, ll mod)
{
ll ret = 1;
for (; p; p >>= 1, base = base * base % mod)
if (p & 1)
ret = ret * base % mod;
return ret;
}

ll CRT(int n, ll *a, ll *m)
{
ll M = 1, ret = 0;
FOR(i, 1, n) M *= m[i];
FOR(i, 1, n)
{
ll w = M / m[i];
ret = (ret + a[i] * w % mod * inv(w, m[i]) % mod) % mod;
}
return (ret + mod) % mod;
}

ll calc(ll n, ll q, ll qk)
{
if (!n) return 1;
ll ret = 1;
FOR(i, 1, qk)
if (i % q) ret = ret * i % qk;
ret = qpow(ret, n / qk, qk);
FOR(i, n / qk * qk + 1, n)
if (i % q) ret = ret * (i % qk) % qk;
return ret * calc(n / q, q, qk) % qk;
}

ll multiLucas(ll n, ll m, ll q, ll qk)
{
int cnt = 0;
for (ll i = n; i; i /= q) cnt += i / q;
for (ll i = m; i; i /= q) cnt -= i / q;
for (ll i = n - m; i; i /= q) cnt -= i / q;
return qpow(q, cnt, qk) * calc(n, q, qk) % qk * inv(calc(m, q, qk), qk) % qk * inv(calc(n - m, q, qk), qk) % qk;
}

ll exLucas(ll n, ll m, ll p)
{
int cnt = 0;
ll qk[20], a[20];//存放所有的 q^k 和待合并答案的结果
for (ll i = 2; i * i <= p; ++i)//质因数分解
{
if (p % i == 0)
{
qk[++cnt] = 1;
while (p % i == 0)
qk[cnt] *= i, p /= i;
a[cnt] = multiLucas(n, m, i, qk[cnt]);
}
}
if (p > 1) qk[++cnt] = p, a[cnt] = multiLucas(n, m, p, p);
return CRT(cnt, a, qk);//CRT 合并答案
}

int main()
{
ll n, m, p;
scanf("%lld %lld %lld", &n, &m, &p);
mod = p;
printf("%lld\n", exLucas(n, m, p));
return 0;
}

习题

两个模板

接下来就是应用到 Lucas 定理的习题了,难度应该是递增的,请放心食用。

[国家集训队]礼物

洛谷 P2183

Description

n 件礼物,送给 m 个人,送给第 i 个人礼物的数量为 w_i 。请计算出送礼物的方案数(两个方案被认为是不同的,当且仅当存在某个人在这两种方案中收到的礼物不同)模 P 后的结果。

数据范围:令 P = \prod_{i = 1}^tp_i^{c_i} ,其中 p_i 为质数,有 1\le n\le10^9 1\leq m\leq 5 1\leq p_i^{c_i}\leq 10^5 1\leq w_i \leq P\leq 10^9

Solution

分析题意:直接一波乘法原理可得答案为

\binom{n}{w_1}\times\binom{n - w_1}{w_2}\times\binom{n - w_1 - w_2}{w_3}\times\cdots\bmod P

(组合意义就是对于每个人看能取多少,第一个人取了 w_1 个了所以第二个人能取的就只有 n - w_1 个,以此类推)

剩下就是套一个 exLucas 板子的事情了(因为 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
#include <cstdio>
#define FOR(i, a, b) for (ll i = a; i <= b; ++i)

typedef long long ll;

ll P, n, m, w[6];

//.......//

int main()
{
scanf("%lld", &P);
scanf("%lld %lld", &n, &m);
ll W = 0;
FOR(i, 1, m) scanf("%lld", w + i), W += w[i];
if (W > n)
{
puts("Impossible");
return 0;
}
ll ans = 1;
FOR(i, 1, m)
{
ans = ans * exLucas(n, w[i], P) % P;
n -= w[i];
}
printf("%lld\n", ans);
return 0;
}

[SDOI2010]古代猪文

洛谷 P2480

Description

远古时期猪文文字总个数为 n

iPig 打算研究古时某个朝代的猪文文字。该朝代流传的猪文文字恰好为远古时期的 1/k ,其中 k n 的一个正约数(可以是 1 n )。

iPig 觉得只要符合文献,每一种 k|n 都是有可能的。他打算考虑到所有可能的 k 。显然当 k 等于某个定值时,该朝的猪文文字个数为 n/k 。然而从 n 个文字中保留下 n/k 个的情况也是相当多的。iPig 预计,如果所有可能的 k 的所有情况数加起来为 p 的话,那么他研究古代文字的代价将会是 g^p

现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字,所以你只需要告诉他答案除以 999911659 的余数就可以了。

数据范围 1\le n,g \le 10^9

Solution

答案实际就为

g^{\sum_{k\mid n}\binom n k}\bmod 999911659

然后为了求这个东西,需要套一个欧拉定理:

g^{\sum_{k\mid n}\binom n k\bmod 999911658}\bmod 999911659

现在问题的关键就是求出

\sum_{k\mid n}\binom n k\bmod 999911658

这波,这波啊直接 exLucas,尝试一下分解 999911658=4679\times3\times2\times35617 ,每一个质因子的次数都是 1 ,所以只需要用 CRT 求解如下方程组

\begin{cases}p \equiv \sum_{k\mid n}\dbinom n k\pmod{2}\\p \equiv \sum_{k\mid n}\dbinom n k\pmod{3}\\p \equiv \sum_{k\mid n}\dbinom n k\pmod{4679}\\p \equiv \sum_{k\mid n}\dbinom n k\pmod{35617}\end{cases}

最后求一波快速幂,于是这题就做完了,注意代码细节即可。、

参考代码:

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
67
68
69
70
71
#include <cstdio>
#define FOR(i, a, b) for (ll i = a; i <= b; ++i)

typedef long long ll;

const ll mod[5] = {999911659, 2, 3, 4679, 35617};

const int maxp = 40005;
ll fact[maxp];

ll qpow(ll base, ll p, ll mod)
{
ll ret = 1;
for (; p; p >>= 1, base = base * base % mod)
if (p & 1) ret = ret * base % mod;
return ret;
}

void init(ll p)
{
fact[0] = 1;
FOR(i, 1, p)
fact[i] = fact[i - 1] * i % p;
return;
}

ll C(int n, int m, ll p)
{
if (n < m) return 0;
return fact[n] * qpow(fact[m], p - 2, p) % p * qpow(fact[n - m], p - 2, p) % p;
}

ll Lucas(ll n, ll m, ll p)
{
if (n < m) return 0;
if (!n || !m) return 1;
return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

ll a[5];

int main()
{
ll n, g;
scanf("%lld %lld", &n, &g);
if (g % mod[0] == 0)//特判
{
printf("0\n");
return 0;
}
FOR(k, 1, 4)
{
init(mod[k]);
for (ll i = 1; i * i <= n; ++i)
{
if (n % i) continue;
a[k] = (a[k] + Lucas(n, i, mod[k])) % mod[k];
if (i * i != n)
a[k] = (a[k] + Lucas(n, n / i, mod[k])) % mod[k];
}
}
ll M = mod[0] - 1, ans = 0;
FOR(i, 1, 4)
{
int w = M / mod[i];
ans = (ans + a[i] * w % M * qpow(w, mod[i] - 2, mod[i]) % M) % M;
}
printf("%lld\n", qpow(g, ans, mod[0]));
return 0;
}

[SHOI2015]超能粒子炮·改

洛谷 P4345

Description

t 组数据( 1\le t\le 10^5 ),给定 n k 1\le n,k\le 10^{18} ),求

\sum_{i = 0}^k\binom n k\bmod{2333}

的值。

Solution

由于数据组数很大并且 n k 都很大,所以不能直接卢卡斯然后简单相加,时间会爆炸。考虑令

f(n, k) = \sum_{i = 0}^k\binom n k\bmod p

其中 p 即为 2333 。然后使用卢卡斯定理拆开

\begin{aligned}f(n,k) &\equiv \sum_{i = 0}^k\binom n k\\&\equiv \sum_{i = 0}^k\binom{n\bmod p}{i\bmod p}\binom{\lfloor\frac np\rfloor}{\lfloor\frac ip\rfloor}\pmod p\end{aligned}

现在化简成了这样之后,注意到 p 其实很小,可以类似整除分块的做法,按照 \displaystyle\left\lfloor\frac ip\right\rfloor 的值分开来处理:

f(n,k) \equiv \binom{\lfloor\frac np\rfloor}{0}\sum_{i = 0}^{p - 1}\binom{n\bmod p}{i} + \binom{\lfloor\frac np\rfloor}{1}\sum_{i = 0}^{p - 1}\binom{n\bmod p}{i} + \cdots+\binom{\lfloor\frac np\rfloor}{\lfloor\frac kp\rfloor}\sum_{i = 0}^{k\bmod p}\binom{n\bmod p}{i}\pmod p

前面有从 0 \displaystyle\left\lfloor\frac kp\right\rfloor - 1 的整块,把前面整块的部分拎出来化简:

\begin{aligned}&\binom{\lfloor\frac np\rfloor}{0}\sum_{i = 0}^{p - 1}\binom{n\bmod p}{i} + \binom{\lfloor\frac np\rfloor}{1}\sum_{i = 0}^{p - 1}\binom{n\bmod p}{i} + \cdots + \binom{\lfloor\frac np\rfloor}{\left\lfloor\frac kp\right\rfloor - 1}\sum_{i = 0}^{p - 1}\binom{n\bmod p}{i}\\=&\left(\sum_{i = 0}^{p - 1}\binom{n\bmod p}{i}\right)\cdot\left(\sum_{i = 0}^{\left\lfloor\frac kp\right\rfloor - 1}\binom{\lfloor\frac np\rfloor}{i}\right)\\=&f(n\bmod p, p - 1)\times f(\lfloor n/p\rfloor, \lfloor k/p\rfloor - 1)\end{aligned}

后面的余项即为

\begin{aligned}&\binom{\lfloor\frac np\rfloor}{\lfloor\frac kp\rfloor}\sum_{i = 0}^{k\bmod p}\binom{n\bmod p}{i}\\=&\binom{\lfloor\frac np\rfloor}{\lfloor\frac kp\rfloor}f(n\bmod p, k\bmod p)\end{aligned}

最后我们得到

f(n, k) =f(n\bmod p, p - 1)\times f(\lfloor n/p\rfloor, \lfloor k/p\rfloor - 1) +\binom{\lfloor\frac np\rfloor}{\lfloor\frac kp\rfloor}f(n\bmod p, k\bmod p)\bmod p

\displaystyle\binom{\lfloor\frac np\rfloor}{\lfloor\frac kp\rfloor} 可以直接 Lucas 定理,剩下的递归做就行,预处理 p 以内的 f 就可以很快的做了。

主要代码:

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
#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; ++i)const int p = 2333;
int C[p + 5][p + 5], f[p + 5][p + 5];

int lucas(int n, int m)
{
if (!m) return 1;
return C[n % p][m % p] * lucas(n / p, m / p) % p;
}

int F(int n, int k)
{
if (k < 0) return 0;
if (!k || !n) return 1;
if (n < p && k < p) return f[n][k];
return (lucas(n / p, k / p) * f[n % p][k % p] % p + f[n % p][p - 1] * F(n / p, k / p - 1) % p) % p;
}

signed main()
{
int t = read();
C[0][0] = 1;
FOR(i, 1, p)
{
C[i][0] = C[i][i] = 1;
FOR(j, 1, i - 1)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
}
f[0][0] = 1;
FOR(i, 1, p)
f[i][0] = 1;
FOR(i, 0, p)
FOR(j, 1, p)
f[i][j] = (C[i][j] + f[i][j - 1]) % p;
while (t--)
{
int n = read(), k = read();
printf("%lld\n", F(n, k));
}
return 0;
}

需要注意预处理 f 的时候 f(0, i) = 1 ,如果这里没处理的话会只有 55pts。

Lucas 定理的另一种证明

参考了**冯志刚版《初等数论》**第37页

Lucas 定理的另一形式

对于整数 a b 和素数 p ,若

\begin{aligned} a &= \sum_{i = 0}^k a_ip^i\\ b &= \sum_{i = 0}^k b_ip^i \end{aligned}

(相当于把 a b p 进制下表示)则

\binom ab\equiv\prod_{i = 0}^k\binom{a_i}{b_i}\pmod p

那么它和之前提到的

\binom a b\equiv\binom{\lfloor\frac ap\rfloor}{\lfloor\frac bp\rfloor}\binom{a\bmod p}{b\bmod p}\pmod p

为什么是等价的呢?

这样子考虑,对 p 取模相当于取了 p 进制下的最低位,而除以 p 向下取整就相当于 p 进制下去掉最后一位,反复套用就发现两个形式是等价的了。

证明

记号约定:设 \displaystyle f(x) = \sum_{i = 0}^na_ix^i \displaystyle g(x) = \sum_{i = 0}^nb_ix^i 均为整系数多项式,若对于 \forall 0\le i\le n ,都有 a_i\equiv b_i\pmod m ,则称 f(x) g(x) 对模 m 同余,记作 f(x)\equiv g(x)\pmod m 。注意到若 f(x)\equiv g(x)\pmod m ,则对于 \forall a\in \mathbb Z ,都有 f(a)\equiv g(a)\pmod m

由于 p 为素数,可知对于 1\le j\le p - 1 ,都有

\binom p j = \frac pj\binom{p - 1}{j - 1}\equiv0\pmod p

所以

\begin{aligned} (1 + x)^p &= 1 + \binom p1x + \cdots + \binom{p}{p - 1}x^{p - 1} + x^p\\ &\equiv 1 + x^p\pmod p \end{aligned}

利用这个结论,有

\begin{aligned} (1 + x)^a &= (1 + x)^{a_0}((1 + x)^p)^{a_1}\cdots((1 + x)^{p^k})^{a_k}\\ &\equiv (1 + x)^{a_9}(1 + x^p)^{a_1}\cdots(1 + x^{p^k})^{a_k}\pmod p \end{aligned}

观察右边展开后得到的结果。发现每个括号中有且仅有一项对 x^b 的系数产生了贡献(根据 p 进制数的性质),再结合二项式定理,故

\binom ab\equiv\prod_{i = 0}^k\binom{a_i}{b_i}\pmod p

总结

那么对于 Lucas 定理及其扩展的学习就告一段落了,除了这些列出来的习题外,Lucas 定理还可能出现在某些毒瘤组合题要你求组合数取模的值的时候,总的来说 Lucas 定理本身还是一个比较清新优美的定理的。

省选爆炸没进省队的蒟蒻祝各位 NOI 加油。

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme