数据结构与算法-数学-基础数学2（扩展欧几里得算法，组合数问题）
六：扩展欧几里得算法
同余：
若 a≡b(modm)，则 m 整除 a−b，即 a=b+km（k 为整数）。
扩展欧几里得算法
扩展欧几里得算法可用于求解 ax+by=gcd(a,b) 的一组整数解。
#include <iostream>
using namespace std;
// 扩展欧几里得算法，用于求解 ax + by = gcd(a, b) 的一组整数解
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 判断方程 ax + by = c 是否有解，并尝试求解
bool solveLinearEquation(int a, int b, int c, int &x, int &y) {
int d = exgcd(a, b, x, y);
if (c % d != 0) {
// 如果 c 不是 gcd(a, b) 的倍数，则方程无解
return false;
}
int k = c / d;
// 得到方程 ax + by = c 的一组特解
x *= k;
y *= k;
return true;
}
int main() {
int a, b, c;
cin >> a >> b >> c;
int x, y;
if (solveLinearEquation(a, b, c, x, y)) {
cout << "方程有解，一组解为: x = " << x << ", y = " << y << endl;
} else {
cout << "方程无解" << endl;
}
return 0;
}
七：组合数
1-：访问次数多，数值较小，使用动态规划法：
当访问次数较多且数据范围较小时，可利用组合数的递推公式
Cnm(n个中m个的组合)=Cn−1m(第n个不选，剩下的n-1个中选m个)+Cn−1m−1(选中n,剩m-1个在其余n-1中选)
进行动态规划求解。
#include <iostream>
using namespace std;
const int N = 2010, MOD = 1e9 + 7;
int c[N][N];
void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
}
}
int main() {
init();
int n;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
cout << c[a][b] << endl;
}
return 0;
}
2-：qmi求组合数（数据范围较大但是访问次数少）
若数据范围较大但访问次数少，可通过快速幂来计算阶乘的逆元，进而计算组合数。若数据较少但访问较多，也可预处理阶乘和阶乘逆元数组。
这里有一个可以把n logn 的时间复杂度降低为 n的一个初始化方法：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010, MOD = 1e9 + 7;
int fact[N], infact[N];
// 快速幂函数
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
// 预处理阶乘和阶乘逆元数组
void init() {
//求出fact （fact[i]表示i!）
intfact[0]=fact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (LL)fact[i - 1] * i % MOD;
}
//通过infact[i]=infact[i+1]×(i+1)mod p 对我们的球infact进行优化
infact[N - 1] = qmi(fact[N - 1], MOD - 2, MOD);
for (int i = N - 2; i >= 1; i--) {
infact[i] = (LL)infact[i + 1] * (i + 1) % MOD;
}
}
int main() {
init();
int n;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
cout << (LL)fact[a] * infact[b] % MOD * infact[a - b] % MOD << endl;
}
return 0;
}
3-:Lucas 定理求组合数（数据量更大，但是模数是质数时）
当数据量更大时，可使用 Lucas 定理来计算组合数。Lucas 定理表述为：
Cnm≡(C(n mod p)(m mod p)×C(n/p)(m/p) )mod p，其中 p 为质数。
这里我们使用最基本的线性的方式求出一个组合数配合lucas定理来计算组合数
#include <iostream>
using namespace std;
typedef long long LL;
// 快速幂函数
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
// 计算 C(a, b) % p
int C(int a, int b, int p) {
if (b > a) return 0;
int res = 1;
for (int i = 1, j = a; i <= b; i++, j--) {
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2, p) % p;
}
return res;
}
// Lucas 定理
int lucas(LL a, LL b, int p) {
if (a < p && b < p) return C(a, b, p);//数据a,b比p小，直接返回答案
return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;//小数据直接用C函数，大的继续调用lucas
}
int main() {
int n;
cin >> n;
while (n--) {
LL a, b;
int p;
cin >> a >> b >> p;
cout << lucas(a, b, p) << endl;
}
return 0;
}
-4：超大数据需要配合高精度乘法和加法
比如a，b都在1~10000的范围内
筛出质数：使用筛法（如埃氏筛法或线性筛法）找出 1 到 10000 内的所有质数。
分解质因数：分别对 a!、b! 和 (a−b)! 进行质因数分解（枚举质数然后获取其在这三个数的权重），统计每个质因数的指数。
计算组合数：通过 Cab 的质因数分解结果，使用高精度乘法计算最终的组合数。
#include <iostream>
#include <vector>
using namespace std;
const int N = 10010;
int primes[N], cnt;
bool st[N];
// 线性筛法求质数
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
// 计算 n! 中质因数 p 的指数
int get(int n, int p) {
int res = 0;
while (n) {
res += n / p;
n /= p;
}
return res;
}
// 高精度乘法
vector<int> mul(vector<int> a, int b) {
vector<int> c;
int t = 0;
for (int i = 0; i < a.size() || t; i++) {
if (i < a.size()) t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
// 计算组合数 C(a, b)
vector<int> combination(int a, int b) {
get_primes(a);
vector<int> res(1, 1);
for (int i = 0; i < cnt; i++) {
int p = primes[i];
// 计算 C(a, b) 中质因数 p 的指数
int s = get(a, p) - get(b, p) - get(a - b, p);
// 累乘质因数 p 的 s 次幂
for (int j = 0; j < s; j++) {
res = mul(res, p);
}
}
return res;
}
int main() {
int a, b;
cin >> a >> b;
vector<int> res = combination(a, b);
for (int i = res.size() - 1; i >= 0; i--) {
cout << res[i];
}
cout << endl;
return 0;
}
相关文章：
数据结构与算法-数学-基础数学2（扩展欧几里得算法，组合数问题）
六：扩展欧几里得算法 同余： 若 a≡b(modm)，则 m 整除 a−b，即 abkm（k 为整数）。 扩展欧几里得算法 扩展欧几里得算法可用于求解 axbygcd(a,b) 的一组整数解。 #include <iostream> using namesp…...
【力扣hot100题】（072）柱状图中的最大矩阵
这绝对是我做过印象最深的算法题之一。（还有是那道盛水最多的贪心题） 当初不知道想了多少个日日夜夜，所幸这道题已经深深的烙印在了我的脑海里。 现在看来也没那么可怕（）不过初见确实非常难想到单调栈。 方法如下&a…...
T-SQL语言的压力测试
T-SQL语言的压力测试 随着数据驱动技术的发展，数据库在现代应用中的角色愈加重要。而在数据库管理系统中，微软的SQL Server凭借其强大的功能和易用性，广泛应用于各行业。在这一环境中，T-SQL（Transact-SQL）…...
debian 系统gnome怎么关闭触摸屏三指滑动
ubuntu如何限制三指手势操作_ubuntu 手势-CSDN博客 参考方案给上面了， kiosk模式 就是专用模式，类似于广告机、售货机那种。 方案 在 Debian 系统的 GNOME 桌面环境中，可以通过以下方法关闭触摸屏三指滑动功能： 安装 gnome-tweaks 工具：...
【9】搭建k8s集群系列（二进制部署）之安装work-node节点组件（kube-proxy）和网络组件calico
承接上一篇文章，继续安装工作节点的第二个组件：kube-proxy 一、创建配置文件 cat > /opt/kubernetes/cfg/kube-proxy.conf << EOF KUBE_PROXY_OPTS"--logtostderrfalse \\ --v2 \\ --log-dir/opt/kubernetes/logs \\ --config/opt/kubern…...
MongoDB及Yapi迁移数据
一、MongoDB安装及迁移 1、导入MongoDB GPG密钥 sudo rpm --import https://www.mongodb.org/static/pgp/server-5.0.asc 2、创建MongoDB 安装源配置文件 vi /etc/yum.repos.d/mongodb-org-5.0.repo，添加以下内容： [mongodb-org-5.0] nameMongoDB Repo…...
高效解读机器语言，profinet转ethernet ip网关烟草企业自动化升级案例分析
工业通信协议转换在烟草生产线的实践应用 某中型烟草生产企业为提高自动化水平，引进了西门子S7-1500系列PLC控制系统和防爆型科氏力质量流量计。但在系统集成阶段，技术人员发现PLC支持的PROFINET协议与流量计采用的EtherNet/IP协议存在互操作障碍&#x…...
使用Scade实现神经网络算法
在ERTS2022中，ANSYS 发表了使用Scade实现神经网络AI算法的相关工作。论文题目为《Programming Neural Networks Inference in a Safety-Critical Simulation-based Framework》 背景与挑战 神经网络在安全关键系统中的应用：随着嵌入式系统中自主性的引入…...
rom定制系列------小米10pro机型定制解锁固件 原生安卓15批量线刷固件 操作解析与界面预览
注意;固件用于自己机型忘记密码或者手机号注销等出现设备锁 过保修期 售后无视的机型，勿用于非法途径 目前有粉丝联系，自己的机型由于手机号注销导致手机更新系统后出现设备锁界面。另外也没有解锁bl。目前无法使用手机。经过询问是小米10pro机型。根据…...
试题速浏、分类及浅析)
2023年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2023年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛（China Undergraduate Mathematical Contest in Modeling）是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动，目的在于激…...
试题速浏、分类及浅析)
2014年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2014年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛（China Undergraduate Mathematical Contest in Modeling）是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动，目的在于激励学生学习数学的积极性，提高学…...
【Docker基础】--查阅笔记1
目录 Docker是什么Docker解决什么问题Docker的理念Docker基本组成镜像（image）容器（container）仓库（registry） Docker平台架构Docker基本实现原理 Docker常用命令总结 Docker是什么 Docker解决什么问题 统…...
算法（动态规划）
动态规划 基本思想 将问题分解为相互重叠的子问题 定义子问题：将原问题分解为若干个子问题。确定状态转移方程：找到子问题之间的递推关系。边界条件：确定初始状态的值。递推计算：根据状态转移方程和边界条件逐步计算子问题的解。…...
2025 年前端与后端开发方向的抉择与展望-优雅草卓伊凡
2025 年前端与后端开发方向的抉择与展望-优雅草卓伊凡 在 2025 年这个科技浪潮奔涌的时代，软件开发领域持续变革，前端与后端开发方向的抉择，成为众多从业者和爱好者亟待破解的关键命题。卓伊凡就频繁收到这样的疑问：“2025 年了&…...
指纹浏览器技术架构解析：高并发批量注册业务的工程化实践——基于分布式指纹引擎与防关联策略的深度实现
一、技术背景与行业痛点 在跨境电商、广告投放、问卷调查等场景中，批量注册与多账号矩阵运营已成为刚需。然而，主流平台（如亚马逊、Facebook、Google）的风控系统通过浏览器指纹追踪（Canvas/WebGL/WebRTC等）…...
)
基于SpringBoot的“智慧医疗采购系统”的设计与实现（源码+数据库+文档+PPT)
基于SpringBoot的“智慧医疗采购系统”的设计与实现（源码数据库文档PPT) 开发语言：Java 数据库：MySQL 技术：SpringBoot 工具：IDEA/Ecilpse、Navicat、Maven 系统展示 系统总体结构图 局部E-R图 系统首页界面 系统…...
codeforces B. Large Array and Segments
题目简述： 给定一个长度为n的数组，以及两个整数k和p，该数组可以通过复制在增加长度，可以复制k次，我们最后要找到保证后缀和至少为p的首元结点的数量 思路简述： 找到有多少个完整的原数组n，最…...
VS Code-i18n Ally国际化插件
前言 本文借鉴：i18n Ally 插件帮你轻松搞定国际化需求-按模块划分i18n Ally 是一款 VS Code 插件，它能通过可视 - 掘金本来是没有准备将I18n Ally插件单独写一个博客的，但是了解过后，功能强大，使用方便，解决…...
：基于ECA注意力机制的ResNet18网络实现)
ResNet改进(21)：基于ECA注意力机制的ResNet18网络实现
一、引言 在计算机视觉领域，ResNet（残差网络）一直是图像分类任务中的重要基准模型。今天我们要介绍的是一个改进版的ResNet18网络，它在传统ResNet结构的基础上加入了ECA（Efficient Channel Attention）注意力机制，能够在不显著增加计算量的情况下提升模型性能。 二、网络…...
[ERROR] Some problems were encountered while processing the POMs
记录一次maven的错误 问题复现： 我在ruoyi-vue-plus项目的ruoyi-modules中新建了一个子项目ruoyi-network-telphonem,然后某一次编译的时候提示SysTenantServiceImpl找不到无参的构造函数，检查了很久都没发现问题，于是我想着删掉本地maven仓…...
【网络协议】WebSocket讲解
目录 webSocket简介 连接原理解析: 客户端API 服务端API（java） 实战案例 （1）引入依赖 （2）编写服务端逻辑 （3）注册配置类 （4）前端连接 WebSocket 示例…...
什么是可靠性工程师？
一、什么是可靠性工程师？ 可靠性工程师就是负责确保产品在使用过程中不出故障、不给客户添麻烦。 你可以理解为是那种“挑毛病的人”，但不是事后挑，是提前想清楚产品在哪些情况下可能会出问题，然后解决掉。 比如： …...
Next.js + SQLite 项目 Docker 生产环境部署方案
以下是完整的 Next.js SQLite 项目 Docker 生产环境部署方案： 1. 项目结构准备 your-project/ ├── prisma/ │ ├── schema.prisma │ └── migrations/ ├── app/ ├── lib/ ├── Dockerfile ├── docker-compose.yml ├── .dockerignore └…...
记录1---20250407
哈佛结构：指令和数据放在不同的存储器，因为在使用流水线时，方便数据和指令的读取和存入。 冯诺依曼结构：指令和数据放在同一个存储器。 处理器的存储结构：CPU内部采用hierarchy 存储结构，一般由 CPU内部…...
php调用大模型应用接口实现流式输出以及数据过滤
最近开发智能客服，需要用php调用已有的大模型应用接口流式输出vue前端调用打字机效果展示。这里整理了php调用大模型流式输出业务过滤等的核心实现部分，分享给大家。 前置条件：大模型应用接口已经打通（最好是通过postman或者apip…...
数据结构：红黑树
为什么要以这个结构为题？那就要追溯到CSTL库中的两种map/set，分别基于红黑树与哈希表，我是根本分不清楚。为了搞清楚其区别，我会重点聊聊红黑树和哈希表。 当然也会简单介绍一下树的结构。 树 Tree 首先需要简单了解树这个数据结…...
nginx配置ssl证书,实现https安全访问.
前置条件: 名称 ip地址端口号nginx服务器192.168.59.3080/443server服务器190.168.59.318080/8081/8082 安装nginx服务: 参见: 编译安装nginx-CSDN博客 启动后端web服务器192.168.59.31: (#后端要被代理的web服务器要有docker服务并且配置相关的加速服务) 拉取tomcat容器…...
《当区块链穿上防弹衣：落盘加密技术全景拆解》
落盘加密是区块链技术中一项重要的数据安全机制，主要用于保护节点本地存储的敏感数据不被非法访问。本文将全面解析区块链落盘加密的技术原理、实施方法、应用价值，并与其他加密技术进行比较分析。 🔒 落盘加密的技术原理 落盘加密(Disk Encryption)是指对存储在物理磁盘…...
新HTML5
在新HTML5中，DOCTYPE声明以及字符编码声明都非常简单： <!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>Document</title> </head> <body>内容 </body> </html>HTM…...
DeepSeek-MLA
MLA 结构 需要缓存 KV 向量共用的压缩隐特征K 向量多头共享的带位置编码的向量 为什么带有位置信息的 Q 向量来自于隐特征向量，而带有位置的 K 向量来自于 H 向量且共享呢？ 最好的方法肯定是从H向量直接计算并且不共享，但是会大大增加显存使…...
SQL：数据类型（Data Types）
目录 数字数据类型（Numeric data types) 非数据类型（Non-numeric data types) 日期和时间类型（Date and Time Types) NULL（缺失或未知值） 当你在数据库中创建表格时，你必须指明表中每一列可以保存的数据…...
AF3 OpenFoldBatchCollator类解读
AlphaFold3 data_modules 模块的 OpenFoldBatchCollator 类将一个蛋白质样本列表中的多个字典按键合并，并对每个键值进行 torch.stack 操作，打包成一个批次（batch）。通过定义 OpenFoldBatchCollator类的 __call__ 方法，可以将类的实例当作函数来调用，相当于自定义的批次打…...
手搓多模态-06 数据预处理
前情回顾 我们目前实现了视觉模型的编码器部分，然而，我们所做的是把一张图片编码嵌入成了许多个上下文相关的嵌入向量，然而我们期望的是一张图片用一个向量来表示，从而与文字的向量做点积形成相似度（参考手搓多模态-01…...
[蓝桥杯] 求和
题目链接 P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷 题目理解 这道题就是公式题，我们模拟出公式后，输出最终结果即可。 本题不难，相信很多同学第一次见到这道题都是直接暴力解题。 两个for循环，测试样例，直接拿下。 #in…...
INFINI Labs 产品更新 | Coco AI 0.3 发布 – 新增支持 Widget 外部站点集成
INFINI Labs 产品更新发布！此次更新涵盖 Coco AI 、Easysearch 等产品多项重要升级，重点提升 AI 搜索能力、易用性及企业级优化。 Coco AI v0.3 作为 开源、跨平台的 AI 搜索工具，新增快捷键设置，支持多个聊天会话等功能。Coco A…...
vue3+element-plus多个多选下拉框并搜索
一、下拉框组件： <template> <div class"top-select"> <div class"first-select"> <div v-for"(group, index) in selectGroups" :key"index" class"item-select" > <div class&quo…...
多类分类与SoftMax回归)
吴恩达深度学习复盘(9)多类分类与SoftMax回归
多类分类 概念 对于分类问题，并非只有0或1两个标签，而是可以有两个以上的开放标签。以手写数字分类问题为例，之前只是区分0和1， 但在实际生活中，如读取信封上的数字或邮政编码，会涉及十个可能的数字识别&…...
【力扣hot100题】（068）有效的括号
犹记得第一次做这题的时候是怎样一番惨状，现在已经得心应手了。 class Solution { public:bool isValid(string s) {stack<char> zhan;for(int i0;i<s.size();i){if(s[i]{||s[i](||s[i][) zhan.push(s[i]);else{if(zhan.empty()) return 0;if(zhan.top(){…...
深度学习篇---Prophet时间序列预测工具
文章目录 前言一、什么是Prophet？易用性自动化灵活性鲁棒性快速拟合 二、Prophet的核心原理1. 趋势模型a. 分段线性模型（默认）b. 逻辑增长模型 2. 季节性模型3. 节假日效应 三、Prophet使用方法安装ProphetPython基本使用示例1. 准备数据2. 创…...
TDengine JAVA 语言连接器
简介 本节简介 TDengine 最重要且使用最多的连接器, 本节内容是以教科书式方式列出对外提供的接口及功能及使用过程中要注意的技术细节，大家可以收藏起来做为今后开发 TDengine 的参考资料。 taos-jdbcdriver 是 TDengine 的官方 Java 语言连接器，Java…...
vue3工程中使用vditor完成markdown渲染并防止xss攻击
vue3工程中使用vditor完成markdown渲染并防止xss攻击 背景环境解决方案引入依赖 组件封装实现效果 背景 做oj系统时，题目使用的时markdown语法字符串,前端查看时需要将markdown转html再渲染到页面上。 环境 vitevue3pnpm 解决方案 引入依赖 pnpm install vdit…...
Java面向对象编程详解
面向对象编程是Java的核心特性之一，它通过类和对象的概念来解决实际问题，使程序设计更加符合人类对事物的认知方式。本文将深入探讨Java中的面向对象编程概念和特性。 1. 面向对象的基本概念 1.1 什么是面向对象？ 面向对象程序设计(Object …...
重温java 系列一 Java基础
文件拷贝的5种方式 传统字节拷贝 public static void main(String[] args) throws IOExecption{try(InputStream is new FileInputStream("source.txt");OutputStream os new FileOutputStream("target.txt")){byte[] buffer new byte[1024];int leng…...
Java基础 4.7
1.成员方法传参机制 引用数据类型的传参机制 引用类型传递的是地址（其实也是值，只不过值是地址），可以通过形参影响实参！ public class MethodParameter01 {public static void main(String[] args) {int[] arr {1,…...
基础IO（一）之回顾C语言文件接口
文章目录 共识原理回顾C文件接口打开文件的方式以w的方式打开文件以a的方式打开文件 stdin & stdout & stderr 共识原理 1.文件内容属性 就算内容是空的，也会有属性，内容和属性(两者都是数据)都要在磁盘当中保存 2.文件分为 打开的文件 和 没…...
PandaAI：一个基于AI的对话式数据分析工具
PandaAI 是一个基于 Python 开发的自然语言处理和数据分析工具，支持问答式（ChatGPT）的数据分析和报告生成功能。PandaAI 提供了一个开源的框架，主要核心组件包含用于数据处理的数据准备层（Pandas）以及实现 …...
Rollup详解
Rollup 是一个 JavaScript 模块打包工具，专注于 ES 模块的打包，常用于打包 JavaScript 库。下面从它的工作原理、特点、使用场景、配置和与其他打包工具对比等方面进行详细讲解。 一、 工作原理 Rollup 的核心工作是分析代码中的 import 和 export 语句…...
【NLP 56、实践 ⑬ LoRA完成NER任务】
目录 一、数据文件 二、模型配置文件 config.py 三、数据加载文件 loader.py 1.导入文件和类的定义 2.初始化 3.数据加载方法 代码运行流程 4.文本编码 / 解码方法 ① encode_sentence()： ② decode()： 代码运行流程 ③ padding()： 代码…...
Unity ViewportConstraint
一、组件功能概述 ViewportConstraint是一个基于世界坐标的UI边界约束组件，主要功能包括： 将UI元素限制在父容器范围内支持自定义内边距（padding）可独立控制水平和垂直方向的约束 二、实现原理 1. 边界计算（世界坐…...
项目实战--路由权限
封装 单独抽象成组件，写一个新的关于路由的NewsRouter.jsx： import SideMenu from "../../components/sandbox/SideMenu"; import TopHeader from "../../components/sandbox/TopHeader"; import { Routes, Route } from "re…...