AcWing 887. 求组合数 III
本题链接：AcWing 887. 求组合数 III
本博客提供本题截图：
本题解析
卢卡斯定理：
我们知道直接进行除法的话会有精度问题，所以我们可以用逆元去求解，关于逆元的求法见：数学知识：快速幂
AC代码
#include <iostream> #include <algorithm> using namespace std; typedef long long LL; int qmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } int C(int a, int b, int p) { if (b > a) return 0; int res = 1; for (int i = 1, j = a; i <= b; i ++, j -- ) { res = (LL)res * j % p; res = (LL)res * qmi(i, p - 2, p) % p; } return res; } int lucas(LL a, LL b, int p) { if (a < p && b < p) return C(a, b, p); return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; } int main() { int n; cin >> n; while (n -- ) { LL a, b; int p; cin >> a >> b >> p; cout << lucas(a, b, p) << endl; } return 0; }
AcWing 888. 求组合数 IV
本题链接：AcWing 888. 求组合数 IV
本博客提供本题截图：
本题解析
这个题就是直接硬算，利用公式直接展开进行计算，注意本题需要用到高精度乘法，高精度乘法的模板见：高精度运算，展开方式如下图：
展开的过程中注意化简：我们把分母和分子使用分解质因数的形式进行化简，分解质因数见：数学知识：质数
AC代码
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 5010; int primes[N], cnt; int sum[N]; bool st[N]; void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } int get(int n, int p) { int res = 0; while (n) { res += n / p; n /= p; } return res; } vector<int> mul(vector<int> a, int b) { vector<int> c; int t = 0; for (int i = 0; i < a.size(); i ++ ) { t += a[i] * b; c.push_back(t % 10); t /= 10; } while (t) { c.push_back(t % 10); t /= 10; } 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(a - b, p) - get(b, p); } vector<int> res; res.push_back(1); for (int i = 0; i < cnt; i ++ ) for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]); for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]); puts(""); return 0; }
