吴忠建设局网站,查找公司信息的网站,聚合页面网站什么时候做,微信公众号是在哪个网站做的目录 1 基础知识2 模板3 工程化 1 基础知识
请明确如下关于取余的基本定理#xff1a;
数a和数b的乘积模上p#xff0c;等于数a模上p和数b模上p的乘积。即#xff0c; ( a ⋅ b ) m o d p ( a m o d p ) ⋅ ( b m o d p ) (a \cdot b ) \ mod \ p (a \ mod \ p) \cdot … 目录 1 基础知识2 模板3 工程化 1 基础知识
请明确如下关于取余的基本定理
数a和数b的乘积模上p等于数a模上p和数b模上p的乘积。即 ( a ⋅ b ) m o d p ( a m o d p ) ⋅ ( b m o d p ) (a \cdot b ) \ mod \ p (a \ mod \ p) \cdot (b \ mod \ p) (a⋅b) mod p(a mod p)⋅(b mod p)数a除以数b的结果模上p并不等于数a模上p除以数b模上p。即 ( a / b ) m o d p ≠ ( a m o d p ) / ( b m o d p ) (a/b)\ mod \ p \neq (a \ mod \ p) / (b \ mod \ p) (a/b) mod p(a mod p)/(b mod p)
一 题目要求求组合数模上p的结果即 C n k m o d p ? C_n^k \ mod\ p ? Cnk mod p? 其中 p 1 e 9 7 p1e97 p1e97是一个质数。
重新考虑组合数 C n k C_n^k Cnk的计算公式 C n k m o d p n ! k ! ⋅ ( n − k ) ! m o d p C_n^k \ mod \ p\frac{n!}{k!\cdot (n-k)!} \ mod \ p Cnk mod pk!⋅(n−k)!n! mod p 记数 k ! k! k!模p的乘法逆元为x数 ( n − k ) ! (n-k)! (n−k)!模p的乘法逆元为y则上式可写成 n ! k ! ⋅ ( n − k ) ! m o d p n ! ⋅ x ⋅ y m o d p ( n ! m o d p ) ⋅ ( x m o d p ) ⋅ ( y m o d p ) \frac{n!}{k!\cdot (n-k)!} \ mod \ pn! \cdot x\cdot y \ mod \ p(n! \ mod \ p)\cdot (x \ mod \ p) \cdot (y \ mod \ p) k!⋅(n−k)!n! mod pn!⋅x⋅y mod p(n! mod p)⋅(x mod p)⋅(y mod p) 那么考虑数 k ! k! k!模p的乘法逆元x由于p是质数故x可由下式计算 x m o d p ( k ! ) p − 2 m o d p x \ mod\ p (k!)^{p-2} \ mod \ p x mod p(k!)p−2 mod p 观察可以推导出其递推公式 ( k ! ) p − 2 m o d p ( ( k − 1 ) ! ) p − 2 ⋅ k p − 2 m o d p (k!)^{p-2} \ mod \ p ((k-1)!)^{p-2}\cdot k^{p-2} \ mod \ p (k!)p−2 mod p((k−1)!)p−2⋅kp−2 mod p 而对于 k p − 2 m o d p k^{p-2}\ mod \ p kp−2 mod p可以快速幂在 O ( l o g N ) O(logN) O(logN)时间复杂度下求解。
故综合上述可以预处理出阶乘和阶乘的逆元那么答案可以表示如下 f a c t [ n ] ⋅ i n f a c t [ k ] ⋅ i n f a c t [ n − k ] m o d p fact[n] \cdot infact[k] \cdot infact[n-k] \ mod \ p fact[n]⋅infact[k]⋅infact[n−k] mod p 将上述过程用代码表述如下
const int N 1e5 10, mod 1e9 7;
int fact[N], infact[N];int qmi(int a, int k, int p) {long long res 1;while (k) {if (k 1) {res res * a % p;} k 1;a (long long)a * a % p;}return res;
}void init() {fact[0] infact[0] 1;for (int i 1; i N; i) {fact[i] (long long)fact[i-1] * i % mod;infact[i] (long long)infact[i-1] * qmi(i, mod - 2, mod) % mod;}return;
}二 题目要求 C n k m o d p C_n^{k} \ mod \ p Cnk mod p 其中 n n n和 k k k的数据范围在 1 0 18 10^{18} 1018之内而 p p p是质数且它的范围在 1 0 6 10^6 106以内。
对于上述特别大的组合数求解一般引入Lucas定理。
Lucas定理当模数p是质数时有以下等式成立 C n k m o d p C n m o d p k m o d p ⋅ C n / p k / p m o d p C_n^k \ mod \ p C_{n \ mod \ p} ^ {k \ mod \ p } \cdot C_{n/p}^{k/p} \ mod \ p Cnk mod pCn mod pk mod p⋅Cn/pk/p mod p 其中 k m o d p k\ mod\ p k mod p和 n m o d p n\ mod\ p n mod p是 p p p以内的数可直接计算组合数 C n m o d p k m o d p C_{n\ mod\ p}^{k \ mod \ p} Cn mod pk mod p而对于 C n / p k / p C_{n/p}^{k/p} Cn/pk/p则递归使用Lucas定理计算。
故代码如下所示
int qmi(int a, int k, int p) {long long res 1;while (k) {if (k 1) res res * a % p;k 1;a (long long)a * a % p;}return res;
}int C(int a, int b, int p) {if (b a) return 0; //无效值返回0long long res 1;for (int i 1, j a; i b; i, --j) {res res * j % p;res res * qmi(i, p - 2, p) % p;}return res;
}int Lucas(long long a, long long b, int p) {if (a p b p) return C(a, b, p); //终止条件return (long long)C(a % p, b % p, p) * Lucas(a / p, b / p, p) % p;
}三 题目要求 C n k ? C_n^k? Cnk? 此处不模上数p了且 n n n和 k k k的数据范围在 1 0 4 10^4 104以内。
上式可以写成 C n k n ! k ! ⋅ ( n − k ) ! C_n^k\frac{n!}{k!\cdot (n-k)!} Cnkk!⋅(n−k)!n! 考虑任意一个数 a a a的阶乘 a ! a! a!的分解质因子 a ! p 1 α 1 ⋅ p 2 α 2 ⋯ p k α k a!p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k} a!p1α1⋅p2α2⋯pkαk 对于 α i \alpha_i αi其中 0 ≤ i ≤ k 0\leq i \leq k 0≤i≤k可以通过如下式快速计算 α i ⌊ a p i ⌋ ⌊ a p i 2 ⌋ ⌊ a p i 3 ⌋ ⋯ \alpha_i\lfloor \frac{a}{p_i} \rfloor \lfloor \frac{a}{p_i^2} \rfloor \lfloor \frac{a}{p_i^3} \rfloor \cdots αi⌊pia⌋⌊pi2a⌋⌊pi3a⌋⋯ 那么可以快速求解出 C n k C_n^k Cnk的分解质因子然后利用高精度乘法将它们相乘即可。
代码如下
#include iostream
#include vectorusing namespace std;const int N 5010;
int primes[N], cnt;
bool st[N];
int sum[N];void get_primes(int n) {//求n以内的质数for (int i 2; i n; i) {if (!st[i]) {primes[cnt] i;}for (int j 0; primes[j] n / i; j) {st[i * primes[j]] true;if (i % primes[j] 0) break;}}return;
}int get(int a, int p) {//求a!中质因子p的幂int res 0;while (a) {res a / p;a / p;}return res;
}vectorint mul(vectorint a, int b) {vectorint c;int t 0;for (int i 0; i a.size() || t; i) {if (i a.size()) {t t a[i] * b;}c.emplace_back(t % 10);t / 10; }while (c.size() 1 c.back() 0) {c.pop_back();}return c;
}int main() {int a, b;cin a b;get_primes(a);for (int i 0; i cnt; i) {int p primes[i];sum[i] get(a, p) - get(b, p) - get(a - b, p);}vectorint res {1};for (int i 0; i cnt; i) {int p primes[i];for (int j 0; j sum[i]; j) {res mul(res, p);}}for (int i res.size() - 1; i 0; --i) {cout res[i];}cout endl;return 0;
}2 模板
暂无。。。
3 工程化
暂无。。。
