济南建设信息网站,义乌市住房和城乡建设局网站,大连做网站的公司,电商网站建设电话文章目录 写在前面算法1#xff1a;朴素算法思路缺点 算法2#xff1a;递推预处理思路时间复杂度#xff1a; O ( n 2 ) O(n^2) O(n2) 算法3#xff1a;阶乘逆元思路时间复杂度#xff1a; O ( n log n ) O(n \log n) O(nlogn)思考#xff1a;读者也可以尝试写 O ( n… 文章目录 写在前面算法1朴素算法思路缺点 算法2递推预处理思路时间复杂度 O ( n 2 ) O(n^2) O(n2) 算法3阶乘逆元思路时间复杂度 O ( n log n ) O(n \log n) O(nlogn)思考读者也可以尝试写 O ( n ) O(n) O(n) 预处理阶乘逆元。 算法4Lucas 定理思路时间复杂度 O ( p × log p n ) O(p \times \log_p n) O(p×logpn) 写在前面
我上次发了一篇题解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^bC_{a-1}^bC_{a-1}^{b-1}(a,b0) Ca01CabCa−1bCa−1b−1(a,b0)
所以我们可以写一个递推函数部分非主要内容已省略
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!} Cabb!(a−b)!a!, Aabb!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) 预处理阶乘逆元。 算法4Lucas 定理
思路
由 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^bC_{\frac{a}{p}}^{\frac{b}{p}} \times C_{a \bmod p}^{b \bmod p}} CabCpapb×Camodpbmodp
因此我们可以写一个递归函数 LL lucas(int a, int b),递归出口是 a k p , b k p a_kp, b_kp akp,bkp 。
递归的过程相当于自上向下将 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 以内规模的数据 最后如果觉得对您有帮助的话点个赞再走吧
