C++: 卢卡斯定理/Lucas 定理 模板 - 求组合数模质数

Test Input Reasoning:\n\n我们先从最简单的情况开始考虑，n=m=1, p=2。\n\n\n\nC++ 代码实现:\n\ncpp\n#include <iostream>\nusing namespace std;\n\nlong long fac[100005];\nlong long inv[100005];\n\nlong long qpow(long long a, long long b, long long mod) {\n long long ans = 1;\n while (b) {\n if (b & 1) ans = ans * a % mod;\n a = a * a % mod;\n b >>= 1;\n }\n return ans;\n}\n\nvoid init(long long p) {\n fac[0] = 1;\n for (int i = 1; i <= p; i++) {\n fac[i] = fac[i - 1] * i % p;\n }\n inv[p] = qpow(fac[p], p - 2, p);\n for (int i = p - 1; i >= 0; i--) {\n inv[i] = inv[i + 1] * (i + 1) % p;\n }\n}\n\nlong long C(long long n, long long m, long long p) {\n if (n < m) return 0;\n return fac[n] * inv[m] % p * inv[n - m] % p;\n}\n\nlong long lucas(long long n, long long m, long long p) {\n if (m == 0) return 1;\n return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;\n}\n\nint main() {\n int T;\n cin >> T;\n while (T--) {\n long long n, m, p;\n cin >> n >> m >> p;\n init(p);\n cout << lucas(n + m, n, p) << endl;\n }\n return 0;\n}\n\n\n\n代码解释:\n\n1. init(p) 函数: 初始化阶乘数组 fac 和逆元数组 inv。\n2. qpow(a, b, mod) 函数: 快速幂求 a^b 模 mod 的值。\n3. C(n, m, p) 函数: 求组合数 C(n, m) 模 p 的值。\n4. lucas(n, m, p) 函数: 使用卢卡斯定理递归求解 C(n+m, n) mod p 的值。\n\n\n使用示例:\n\n\n2\n1 2 5\n2 1 5\n\n\n\n输出:\n\n\n3\n3\n\n\n\n注意:\n\n* 卢卡斯定理适用于 p 为质数的情况。\n* 代码中使用的模运算 % 可以确保结果在 p 的范围内。\n* 代码可以处理较大的 n 和 m 值，因为使用了递归和快速幂。\n\n\n参考:\n\n* 卢卡斯定理 - 百度百科\n* 组合数模质数 - OI Wiki