Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
173637 | C班-赵奕博 | 组合数的高精度算法 | C++ | 无测评数据 | 0 | 0 MS | 0 KB | 1251 | 2024-08-20 22:30:19 |
#include<bits/stdc++.h> using namespace std; vector<int> multiply(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; } vector<int> factorial(int n) { vector<int> res = {1}; for (int i = 2; i <= n; i++) { res = multiply(res, i); } return res; } int combination(int m, int n) { vector<int> a = factorial(m + n - 2); vector<int> b = factorial(m - 1); vector<int> c = factorial(n - 1); vector<int> res = a; for (int i = 0; i < b.size(); i++) { res[i] -= b[i]; if (res[i] < 0) { res[i + 1]--; res[i] += 10; } } for (int i = 0; i < c.size(); i++) { res[i] -= c[i]; if (res[i] < 0) { res[i + 1]--; res[i] += 10; } } int i = res.size() - 1; while (i > 0 && res[i] == 0) i--; for (; i >= 0; i--) cout << res[i]; cout << endl; return 0; } int main() { int m, n; cin >> m >> n; combination(m, n); return 0; }