题目大意
已知 \(C(m, n) = m! / (n!(m - n)!)\), 输入整数 \(p\), \(q\), \(r\), \(s\)(\(p ≥ q\), \(r ≥ s\), \(p\), \(q\), \(r\), \(s ≤ 10000\)), 计算 \(C(p, q) / C(r, s)\). 输出保证不超过 \(10^8\), 保留 \(5\) 位小数
题解
这道题还是挺水吧...
首先如果直接算出 \(C(p, q)\) 和 \(C(r, s)\) 是肯定不可能的, C++ 存不下这么大的数.
这时候就要用到唯一分解定理, 根据组合数的定义, 显然分子分母可以约分, 那么就可以先预处理出小于 10000 的每个质数, 并求出 \(p!\), \(q!\), \((p - q)!\), \(r\), \(s\), \((r - s)!\) 的每个质因子的幂, 进而表示出 \(C(p, q) / C(r, s)\), 最后用 cmath 库中的 pow 函数计算就可以了.
当然这道题也可以暴力边乘边除来防止答案太大, 虽然精度损失有点大但也可以过这道题了
代码
唯一分解定理:
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <cstring>
- std::vector<int> prime;
- int power[10000];
- int p, q, r, s;
- double ans;
- bool is_prime[10000];
- inline void AddInteger(register int, const int&);
- inline void AddFactorial(const int&, const int&);
- int main(int argc, char const *argv[]) {
- freopen("test.txt", "w", stdout);
- memset(is_prime, 1, sizeof(is_prime));
- is_prime[0] = is_prime[1] = 0;
- for (register int i(2); i <= 10000; ++i) {
- if (is_prime[i]) {
- prime.push_back(i);
- for (register int j(2); i * j <= 10000; ++j) {
- is_prime[i * j] = 0;
- }
- }
- }
- while (~scanf("%d %d %d %d", &p, &q, &r, &s)) {
- memset(power, 0, sizeof(power));
- AddFactorial(p, 1),
- AddFactorial(q, -1),
- AddFactorial(p - q, -1),
- AddFactorial(r, -1),
- AddFactorial(s, 1),
- AddFactorial(r - s, 1);
- ans = 1.0;
- for (auto i : prime) {
- ans *= pow(double(i), double(power[i]));
- }
- printf("%.5lf\n", ans);
- }
- return 0;
- }
- inline void AddInteger(register int n, const int &d) {
- for (auto i : prime) {
- if (n == 1) break;
- while (!(n % i)) {
- n /= i,
- power[i] += d;
- }
- }
- }
- inline void AddFactorial(const int &n, const int &d) {
- for (register int i(1); i <= n; ++i) {
- AddInteger(i, d);
- }
- }
暴力:
- #include <cstdio>
- #include <algorithm>
- double ans, p, q, r, s;
- int main(int argc, char const *argv[]) {
- while (~scanf("%lf %lf %lf %lf", &p, &q, &r, &s)) {
- q = std::min(q, p - q),
- s = std::min(s, r - s);
- ans = 1.0;
- for (register double i(1.0); i <= q || i <= s; ++i) {
- if (i <= q) ans = ans * (p - q + i) / i;
- if (i <= s) ans = ans / (r - s + i) * i;
- }
- printf("%.5lf\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2783810.html