数学-求组合数 IV-大整数模拟
2022/7/27 23:25:35
本文主要是介绍数学-求组合数 IV-大整数模拟,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C++
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; }
这篇关于数学-求组合数 IV-大整数模拟的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?