数学-求组合数 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-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解