组合数(费马小定理, 快速幂)

给定 n 组询问,每组询问给定两个整数 a,b,请你输出 Cbamod(109+7)的值。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一组 a 和 b。

输出格式

共 n 行,每行输出一个询问的解。

数据范围

1≤n≤10000,
1≤b≤a≤105

输入样例:
3
3 1
5 3
2 2
输出样例:
3
10
1

使用快速幂求解a!,用费马小定理求解后面的逆元

代码:

#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 1e9 + 7;

ll n, a, b;
ll fact[N], ifact[N];

ll qmi(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    fact[0] = 1;
    ifact[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fact[i] = fact[i - 1] * i % mod;
        ifact[i] = ifact[i - 1] * qmi(i, mod - 2) % mod;
    }
}

int main() {
    init();
    cin >> n;
    while (n -- ) {
        cin >> a >> b;
        cout << (fact[a] * ifact[b]) % mod * ifact[a - b] % mod << endl;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/525622.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

战争中的AI应用:道德、伦理与技术的交织

AI在战争中的应用是一个极具争议和复杂的话题&#xff0c;无法简单地回答是好还是坏。其影响取决于多个因素&#xff0c;包括使用方式、目的、伦理框架以及技术本身的发展水平。 一方面&#xff0c;AI在战争中具有潜在的积极作用。它可以提高军事行动的效率和精确性&#xff0c…

持续交付工具Argo CD的部署使用

Background CI/CD&#xff08;Continuous Integration/Continuous Deployment&#xff09;是一种软件开发流程&#xff0c;旨在通过自动化和持续集成的方式提高软件交付的效率和质量。它包括持续集成&#xff08;CI&#xff09;和持续部署&#xff08;CD&#xff09;两个主要阶…

自然语言处理技术(Natural Language Processing)知识点

自然语言处理知识点 自然语言处理1. word2vec是什么2. 常用的NLP工具和软件3. 朴素贝叶斯分类器4. BiLSTM-CRF模型怎么去实现5. Bert模型实现NER6. 命名实体识别任务中&#xff0c;怎么去处理数据分布不均的问题&#xff1f;7. 用户问题检索相关文本时&#xff0c;具体都用了哪…

Mac下用adb命令安装apk到android设备笔记

查询了些资料记录备用。以下是在Mac上使用命令行安装APK文件的步骤&#xff1a; 1. 下载并安装ADB&#xff1a; 如果您的Mac上没有安装ADB&#xff0c;请从官方的Android开发者网站下载Android SDK Platform Tools&#xff1a;Android SDK Platform Tools。将下载的ZIP文件解…

KylinOS银河麒麟安装部署AI服务

KylinOS银河麒麟安装部署AI服务&#xff08;CPU版本&#xff09; 查看操作系统 [jnapp8160fcc7cf1b ~]$ nkvers ############## Kylin Linux Version ################# Release: Kylin Linux Advanced Server release V10 (Lance)Kernel: 6.2.0-36-genericBuild: Kylin Linux…

数据挖掘及其近年来研究热点介绍

&#x1f380;个人主页&#xff1a; https://zhangxiaoshu.blog.csdn.net &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️&#xff0c;如有错误敬请指正! &#x1f495;未来很长&#xff0c;值得我们全力奔赴更美好的生活&…

什么是mka音频格式?mp3与mka音频的区别 如何把mp3转成mka格式?

一&#xff0c;什么是mka音频格式 mka音频是一种音频文件格式&#xff0c;它是Matroska多媒体容器格式的一种变体&#xff0c;专门用于存储音频数据。mka文件通常包含压缩的音频流&#xff0c;如MP3、AAC或FLAC等&#xff0c;以及其他可能的元数据&#xff0c;如专辑封面、艺术…

24 个Intellij IDEA好用插件

24 个Intellij IDEA好用插件 一. 安装插件 Codota 代码智能提示插件 只要打出首字母就能联想出一整条语句&#xff0c;这也太智能了&#xff0c;还显示了每条语句使用频率。 原因是它学习了我的项目代码&#xff0c;总结出了我的代码偏好。 Key Promoter X 快捷键提示插件 …

基于ARM内核的智能手环(day7)

RTC&#xff08;实时时钟&#xff09; 什么是RTC&#xff1f; RTC是指实时时钟&#xff08;Real-Time Clock&#xff09;&#xff0c;是一种能够持续跟踪时间的计时器&#xff0c;即使在设备断电的情况下也能保持时间的准确性。它通常用于需要准确时间记录的应用&#xff0c;…

[每日算法 - 阿里机试] leetcode739. 每日温度

入口 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/daily-temperatures/descr…

深度学习理论基础(七)Transformer编码器和解码器

学习目录&#xff1a; 深度学习理论基础&#xff08;一&#xff09;Python及Torch基础篇 深度学习理论基础&#xff08;二&#xff09;深度神经网络DNN 深度学习理论基础&#xff08;三&#xff09;封装数据集及手写数字识别 深度学习理论基础&#xff08;四&#xff09;Parse…

UE5、CesiumForUnreal实现加载建筑轮廓GeoJson数据生成白模功能

1.实现目标 在UE5.3中,通过加载本地建筑边界轮廓面GeoJson数据,获取底面轮廓和楼高数据,拉伸生成白模,并支持点选高亮。为防止阻塞Game线程,使用了异步任务进行优化,GIF动图如下所示: 其中建筑数量:128871,顶点索引数量:6695748,三角面数量:2231916,顶点数量:165…

golang 归并回源策略

前言 下面是我根据业务需求画了一个架构图&#xff0c;没有特别之处&#xff0c;很普通&#xff0c;都是我们常见的中间件&#xff0c;都是一些幂等性GET 请求。有一个地方很有意思&#xff0c;从service 分别有10000 qps 请求到Redis&#xff0c;并且它们的key 是一样的。这样…

CSS - 你遇到过动画卡顿的问题吗

难度级别:中高级及以上 提问概率:70% 回答这道题,首先要说的就是,浏览器在每一帧动画里大概做了什么事情。首先浏览器会执行Javascript,或是操作DOM元素,紧接着需要对DOM元素进行样式计算,当计算完成后,就需要针对DOM元素的位置以及大小…

2024年MathorCup妈妈杯数学建模思路D题思路解析+参考成品

1 赛题思路 (赛题出来以后第一时间在群内分享&#xff0c;点击下方群名片即可加群) 2 比赛日期和时间 报名截止时间&#xff1a;2024年4月11日&#xff08;周四&#xff09;12:00 比赛开始时间&#xff1a;2024年4月12日&#xff08;周五&#xff09;8:00 比赛结束时间&…

oracle hang分析使用

oracle hang分析测试 使用hang分析大部分原因在于产生锁资源的争用 1-2:只有hanganalyze输出&#xff0c;不dump任何进程 3&#xff1a;Level2Dump出在IN_HANG状态的进程 4&#xff1a;Level3Dump出在等待链里面的blockers(状态为LLEAF/LEAF_NW/IGN_DMP&#xff09; 5&…

软件设计师29--并发控制

软件设计师29--并发控制 考点1&#xff1a;事务的特性例题&#xff1a; 考点2&#xff1a;并发问题并发产生的问题丢失更新不可重复读问题读“脏”数据 考点3&#xff1a;封锁协议例题&#xff1a; 考点1&#xff1a;事务的特性 原子性&#xff08;Atomicity&#xff09;&…

好文阅读-数据库-CREATE TABLE AS

添加链接描述 收获如下&#xff1a; 1 DROP DELETE TRUNCATE对比 2 CREATE TABLE AS 这种方式创建表不会复制表的索引&#xff0c;主键&#xff0c;外键约束&#xff0c;包括自增ID。因此应该使用 CREATE TABLE LIKE。 3 数据的处理可以通过建立临时表的方式&#xff0c;之后还…

【实战解析】YOLOv9全流程训练至优化终极指南

【实战解析】YOLOv9全流程训练至优化终极指南 0.引言1.环境准备2.数据预处理&#xff08;1&#xff09;数据准备&#xff08;2&#xff09;按比例划分数据集&#xff08;3&#xff09;xml转txt脚本&#xff08;4&#xff09;配置文件 3.模型训练&#xff08;1&#xff09;单GPU…

超越基准 | 基于每个高斯变形的3D高斯溅射方法及其高效训练策略

作者&#xff1a;小柠檬 | 来源&#xff1a;3DCV 在公众号「3DCV」后台&#xff0c;回复「原论文」可获取论文pdf 添加微信&#xff1a;dddvision&#xff0c;备注&#xff1a;3D高斯&#xff0c;拉你入群。文末附行业细分群 详细内容请关注3DCV 3D视觉精品课程&#xff1a;…