写在前面
我上次发了一篇题解：C++排列与组合算法详解
最开始，我是抱着水题解的想法写的，但却成为了阅读量 最高 的文章，没有之一。
所以今天咱们来重制一篇文章，介绍几个进阶优化版的算法。
算法1：朴素算法
思路
具体见 C++排列与组合算法详解
缺点
不能将结果取模，因为朴素的组合公式在取模意义下没用。
算法2：递推预处理
思路
我们发现：
C
a
0
=
1
C
a
b
=
C
a
−
1
b
+
C
a
−
1
b
−
1
(
a
,
b
>
0
)
C_a^0 = 1\\ C_a^b=C_{a-1}^b+C_{a-1}^{b-1}(a,b>0)
Ca0=1Cab=Ca−1b+Ca−1b−1(a,b>0)
所以我们可以写一个递推函数（部分非主要内容已省略）：
void init_C()
{
for (int i = 0; i < N; i ++ ) // N 表示预处理最大的下标
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
}
再预处理阶乘：
void f(int n)
{
f[0] = 1;
for (int i = 1; i <= n; i ++ )
f[i] = (LL)f[i - 1] * i % P;
}
需要排列的话还可以预处理排列：
void init_A(int n)
{
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= i; j ++ )
a[i][j] = (LL)f[i - j] * c[i][j] % P;
}
时间复杂度： O ( n 2 ) O(n^2) O(n2)
可以处理 5000 5000 5000 以内规模的数据
算法3：阶乘逆元
思路
根据费马小定理可得，当
p
p
p 为质数时，
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1} \equiv 1\pmod p
ap−1≡1(modp)
∴
a
p
−
2
≡
1
a
(
m
o
d
p
)
\therefore a^{p-2} \equiv \frac{1}{a}\pmod p
∴ap−2≡a1(modp)
这就是乘法逆元，通常使用在需要除法取模的情况。
这里再次提一下排列、组合公式： C a b = a ! b ! ( a − b ) ! , A a b = a ! b ! C_a^b=\frac{a!}{b!(a-b)!},\ \ A_a^b=\frac{a!}{b!} Cab=b!(a−b)!a!, Aab=b!a!
求逆元需要用到快速幂：
LL qpow(LL a, LL b, LL p)
{
LL res = 1;
while (b)
{
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
然后预处理阶乘和阶乘逆元：
f[0] = uf[0] = 1;
for (int i = 1; i < N; i ++ )
{
f[i] = (LL)f[i - 1] * i % mod;
uf[i] = (LL)uf[i - 1] * qpow(i, mod - 2, mod) % mod;
}
同样的，如果输出排列、组合结果的话需要利用公式。
时间复杂度： O ( n log n ) O(n \log n) O(nlogn)
可以处理 1 0 5 10^5 105 以内规模的数据
思考：读者也可以尝试写 O ( n ) O(n) O(n) 预处理阶乘逆元。
算法4：Lucas 定理
思路
由 Lucas 定理可得：当 p p p 为质数时，
C a b = C a p b p × C a m o d p b m o d p \large{C_a^b=C_{\frac{a}{p}}^{\frac{b}{p}} \times C_{a \bmod p}^{b \bmod p}} Cab=Cpapb×Camodpbmodp
因此，我们可以写一个递归函数 LL lucas(int a, int b),递归出口是
a
k
<
p
,
b
k
<
p
a_k<p, b_k<p
ak<p,bk<p 。
递归的过程相当于自上向下将 C a 1 b 1 , C a 2 b 2 , … , C a k b k C_{a_1}^{b_1},C_{a_2}^{b_2},…,C_{a_k}^{b_k} Ca1b1,Ca2b2,…,Cakbk 添加到乘式里。
LL lucas(LL a, LL b)
{
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
这里面的 C(a, b) 是指 算法3 ，即用阶乘和阶乘逆元求组合数。
LL qpow(LL a, LL b, LL p)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
LL C(LL a, LL b)
{
LL res = 1;
for (int i = 1, j = a; i <= b; i ++ , j -- )
{
res = (LL)res * j % p;
res = (LL) res * qpow(i, p - 2, p) % p;
}
return res;
}
同样的，如果输出排列、组合结果的话需要利用公式。
时间复杂度： O ( p × log p n ) O(p \times \log_p n) O(p×logpn)
可以处理 a , b ≤ 1 0 18 , p ≤ 1 0 5 a,b \le 10^{18},p \le 10^5 a,b≤1018,p≤105 以内规模的数据
文章来源：https://www.toymoban.com/news/detail-643645.html
最后，如果觉得对您有帮助的话，点个赞再走吧！文章来源地址https://www.toymoban.com/news/detail-643645.html
到了这里，关于【C++】 排列与组合算法详解（进阶篇）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
