Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
173637 C班-赵奕博 组合数的高精度算法 C++ 无测评数据 0 0 MS 0 KB 1251 2024-08-20 22:30:19

Tests(0/0):


#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; }