本文只解决一个问题：求.
递归公式（杨辉三角)
原理
众所周知， .
可以从组合数的现实意义上证明其正确性：
表示从a个不同物体中选出b个的所有方案数。
设a个物体中有一个物体x，则可以分为 包含x的方案
和不包含x的方案。
- 包含x， 则还需要从剩余的a-1个物体中再选b-1个， 即为
- 不包含x， 则需要从另外的a-1个物体中选b个， 即为
因此， .
使用此公式可以以的时间复杂度预处理出范围中所有的组合数。
此方法适用于a*b在范围内且需要频繁查询的问题。
代码实现
c++
1
2
3
4
5
6
| for (int i = 0; i <= n; i ++) {
C[i][0] = 1;
for (int j = 0; j <= i; j ++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
}
}
|
阶乘公式
原理
众所周知， .
可以从排列数的角度证明其正确性：
表示有先后顺序的从a个不同物体中选出b个的所有方案数，。
若只选取固定的b个物品， 则选取顺序显然有种。
即,
通常的， 可以预处理 1~a的阶乘以及阶乘的逆元， 如此一来使用的时间复杂度预处理， 即可的完成每次查询。
但有一个值得注意的问题是， 既然需要计算逆元，
就得保证各阶乘的逆元存在。当p大于a时， 1~a的阶乘必然是存在的，
因为x与p互质、y与p互质， 则x*y同样也与p互质。
所以此方法适用于a小于且a小于p的问题。
代码实现
1
2
3
4
5
| fact[0] = inv[0] = 1;
for (int i = 1; i <= n; i ++) {
fact[i] = (fact[i - 1] * i) % p;
inv[i] = (inv[i-1] * modPow(i, p - 2, p)) % p;
}
|
Lucas定理
原理
Lucas定理:
对于素数p， 有 Lucas定理常见的应用场景是: a非常大， 而p较小。
在实现时， 因为p比较小， 我们一般直接计算. 而则递归的使用Lucas定理计算。
代码实现
1
2
3
| ll lucas(ll a, ll b, ll p) {
return b == 0 ? 1 % p : C(a % p, b % p, p) * lucas(a / p, b / p, p) % 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
34
35
36
| # include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5;
ll fact[N], inv[N];
ll modPow(ll a, ll n, ll p) {
ll res = 1 % p;
while (n) {
if (n & 1) res = res * a % p;
a = a * a % p, n >>= 1;
}
return res;
}
ll C(ll a, ll b, ll p) {
return fact[a] * inv[b] % p * inv[a - b] % p;
}
ll lucas(ll a, ll b, ll p) {
return b == 0 ? 1 % p : C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main () {
int n; cin >> n;
while (n -- ) {
ll a, b, p; cin >> a >> b >> p;
fact[0] = inv[0] = 1 % p;
for (ll i = 1; i < p; i ++) {
fact[i] = fact[i - 1] * i % p;
inv[i] = inv[i - 1] * modPow(i, p - 2, p) % p;
}
cout << lucas(a, b, p) << endl;
}
return 0;
}
|
时间复杂度
函数的执行次数显然是左右次，
而每次执行的时间复杂度取决于函数。
- 如果像如上代码一样， 预处理p内的阶乘fact和逆元inv，
则C函数的时间复杂度为,
lucas算法的时间复杂度为
- 如果不予记录， 而是每次都在C函数内递推一遍，
则C函数的时间复杂度为,
lucas算法的时间复杂度为.
参考
二项式系数 -
维基百科，自由的百科全书 (wikipedia.org)
排列组合 - OI
Wiki (oi-wiki.org)
卢卡斯定理 -
OI Wiki (oi-wiki.org)
卢卡斯定理 -
维基百科，自由的百科全书 (wikipedia.org)
算法学习笔记(25):
卢卡斯定理 - 知乎 (zhihu.com)