AcWing 888. 求组合数 IV
/* * 题目描述: * AcWing 888. 求组合数 IV * 输入 a, b,求 C(a, b) 的值。 * 注意结果可能很大,需要使用高精度计算。 * * 输入格式 * 共一行,包含两个整数 a 和 b。 * * 输出格式 * 共一行,输出 C(a, b) 的值。 * * 数据范围 * 1 ≤ b ≤ a ≤ 5000 * 解决思路: * 非常经典的问题,直接大整数模拟即可,因为这不含任何的质数求余等操作 * */ #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> using namespace std; void show(vector<int> x) { for (int i = x.size() - 1; i >= 0; i -- ) { printf("%d", x[i]); } puts(""); } vector<int> mult(vector<int> A, int b) { int t = 0; vector<int> res; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) { t += A[i] * b; } res.push_back(t % 10); t /= 10; } return res; } vector<int> div(vector<int> A, int b) { vector<int> res; int t = 0; for (int i = A.size() - 1; i >= 0; i -- ) { t = t * 10 + A[i]; res.push_back(t / b); t %= b; } reverse(res.begin(), res.end()); while (res.back() == 0) { res.pop_back(); } return res; } vector<int> solution(int a, int b) { vector<int> res{1}; for (int i = a; i >= a - b + 1; i -- ) { res = mult(res, i); } for (int i = 1; i <= b; i ++ ) { res = div(res, i); } return res; } int main() { int a, b; scanf("%d%d", &a, &b); vector<int> res = solution(a, b); show(res); return 0; }