AcWing算法基础课笔记——求组合数3

求组合数Ⅲ

20万组数据, 1 ≤ b ≤ a ≤ 1 0 18 , 1 ≤ p ≤ 1 0 5 1 \le b \le a \le 10^{18}, 1\le p \le 10 ^5 1ba1018,1p105,使用卢卡斯定理。

卢卡斯定理:
C a b ≡ C a m o d p b m o d p C a / p b / p ( m o d p ) C_a^b \equiv C_{a mod p}^{b mod p}C_{a /p}^{b / p} (mod p) CabCamodpbmodpCa/pb/p(modp)
时间复杂度为 O ( l o g p N ⋅ p l o g p ) O(log _p N \cdot plogp) O(logpNplogp)

题目

在这里插入图片描述

代码

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int p;

int qmi(int a, int k){
	int res = 1;
	while(k) {
		if(k & 1) res = (LL) res * a % p;
		a = (LL) a * a % p;
		k >>= 1;
	}
	return res;
}

int C(int a, int b) {
	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;
	}
	return res;
}

int lucas(LL a, LL b) {
	if(a < p && b < p) return C(a, b);
	return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main() {
	int n;
	cin >> n;
	while(n -- ) {
		LL a, b;
		cin >> a >> b >> p;
		cout << lucas(a, b) << endl;
	}
	return 0;
}

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

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

相关文章

【Hadoop学习笔记】认识Hadoop

认识Hadoop 从网上找的课程做的笔记&#xff0c;有些图是自己理解画的&#xff0c;可能不正确&#xff0c;可以作为参考&#xff0c;有疑问的地方请直接指出&#xff0c;共同交流。 Hadoop是由Apache基金会开发的一个分布式系统基础架构&#xff0c;主要解决海量数据的存储和海…

oracle 主从库中,从库APPLIED为YES ,但是主库任然为NO

主库 从库 从库已经APPLIED但是主库为APPLIED&#xff0c; 主数据库和备用数据库之间的ARCH-RFS心跳Ping负责更新主数据库上v$archived_log的APPLICED列。 在主数据库上有一个指定的心跳ARCn进程来执行此Ping。如果此进程开始挂起&#xff0c;它将不再与远程RFS进程通信&#…

领先GPT-4o:Anthropic 推出新一代模型 Claude 3.5 Sonnet|TodayAI

Anthropic&#xff0c;全球领先的人工智能实验室之一&#xff0c;近日发布了其最新的人工智能模型——Claude 3.5 Sonnet。该模型不仅速度更快&#xff0c;成本更低&#xff0c;而且在多个关键任务上的表现超过了其前代模型 Claude 3 Opus。 更强的视觉功能与幽默感 Claude 3…

【SpringCloud】OpenFeign-远程调用

本文基于上一篇http://t.csdnimg.cn/0qm2R 的基础上添加OpenFeign的使用。 微服务通信 在微服务架构中&#xff0c;微服务之间的通信通常有两种方式&#xff1a;RPC 和 HTTP。在 Spring Cloud 中&#xff0c;默认使用 HTTP 进行微服务的通信&#xff0c;最常用的实现形式有两…

C#使用Scoket实现服务器和客户端互发信息

20240616 By wdhuag 目录 前言&#xff1a; 参考&#xff1a; 一、服务器端&#xff1a; 1、服务器端口绑定&#xff1a; 2、服务器关闭&#xff1a; 二、客户端&#xff1a; 1、客户端连接&#xff1a; 2、客户端断开&#xff1a; 三、通讯&#xff1a; 1、接收信…

【动态规划】简单多状态dp问题

一、经验总结 在分析dp问题的状态表示时&#xff0c;发现当前阶段的状态可以继续细分为多个状态&#xff0c;且多个状态之间可以通过某种方式进行转换&#xff0c;这就是动态规划的多状态问题。 多状态问题的关键有以下几点&#xff1a; 找出dp问题的多个状态表示&#xff1a…

MATLAB-SSA-CNN-SVM,基于SSA麻雀优化算法优化卷积神经网络CNN结合支持向量机SVM数据分类(多特征输入多分类)

MATLAB-SSA-CNN-SVM,基于SSA麻雀优化算法优化卷积神经网络CNN结合支持向量机SVM数据分类(多特征输入多分类) 1.数据均为Excel数据&#xff0c;直接替换数据就可以运行程序。 2.所有程序都经过验证&#xff0c;保证程序可以运行。 3.具有良好的编程习惯&#xff0c;程序均包含…

Vue.JS中如何监听生命周期事件?

目录 一、Vue.JS框架介绍二、Vue.JS的监听事件三、Vue.JS的生命周期事件四、Vue.JS中如何监听生命周期事件 一、Vue.JS框架介绍 Vue.js是一个用于构建用户界面的渐进式JavaScript框架。它设计得非常灵活&#xff0c;可以轻松地被集成到现有的项目中&#xff0c;也可以作为一个…

52、U-boot2023的移植教程

uboot&#xff1a;https://ftp.denx.de/pub/u-boot/ nxp-uboot&#xff1a;https://github.com/nxp-imx/uboot-imx 1、顶层Makefile 文件加入编译的两种方式&#xff1a;以xxx/xxx.c文件为例 1、使用menuconfig: 先编辑.c所在目录下的Kconfig&#xff0…

CCS提示No XDCtools,equivalent...怎么办

摘要&#xff1a;本文介绍CCS( Version: 12.7.0.00007 )编译TI毫米波雷达遇到的No XDCtools&#xff0c;equivalent to the specified version 3.50.8.24_core,are available - defaulting to 3.62.1.16_core.问题的解决方法。 解决这个问题的方法是下载所需要的版本。上图所示…

38 - 换座位(高频 SQL 50 题基础版)

38 - 换座位 -- 方法一 select(casewhen id%21 and id(select max(id) from seat) then idwhen id%20 then id-1else id1end) as id, student fromseat order byid;-- 方法二selectif(id%20,id-1,if(id(select max(id) from Seat),id,id1)) as id,student fromSeat order by id…

1996年-2023年 全国298个地级市-外商直接投资FDI(数据收集)

外商直接投资&#xff08;FDI&#xff09;是一种跨国界的经济活动&#xff0c;它涉及外国投资者在中国境内进行的直接投资行为。这种投资行为不仅包括以货币、实物、技术等形式的资本投入&#xff0c;还可能包括开办独资企业、合资企业、合作企业&#xff0c;以及参与资源开发等…

【网络安全常用术语解读 :什么是0day、1day、nday漏洞】

脆弱性攻击的时间窗被称作脆弱性窗口。通常情况下&#xff0c;一个安全漏洞的时间越久&#xff0c;攻击者就会有更多的机会去攻击它。 2. 0day 漏洞 0天漏洞&#xff0c;也被称作"零日漏洞"&#xff0c;是指尚未由供应商公布的缺陷&#xff0c;表示攻击者已知晓该缺…

CentOS 7、Debian、Ubuntu,这些是什么意思

CentOS 7、Debian、Ubuntu 都是基于 Linux 内核的操作系统&#xff0c;它们各自有不同的特性和用途。以下是对它们的详细解释&#xff1a; CentOS 7 CentOS&#xff08;Community ENTerprise Operating System&#xff09; 是一个基于开源的 Linux 发行版。CentOS 7 是 CentOS …

摄像头画面显示于unity场景

&#x1f43e; 个人主页 &#x1f43e; &#x1faa7;阿松爱睡觉&#xff0c;横竖醒不来 &#x1f3c5;你可以不屠龙&#xff0c;但不能不磨剑&#x1f5e1; 目录 一、前言二、UI画面三、显示于场景四、结语 一、前言 由于标题限制&#xff0c;这篇文章主要是讲在unity中调用摄…

基于JSP的教学质量评价系统

开头语&#xff1a; 你好&#xff0c;我是计算机学长猫哥。如果您对教学质量评价系统感兴趣或有相关需求&#xff0c;欢迎随时联系我。 开发语言&#xff1a; Java 数据库&#xff1a; MySQL 技术&#xff1a; JSP技术 Java语言 工具&#xff1a; MyEclipse、Tomcat服…

华为Mate 70系列,将首发搭载纯血鸿蒙正式版,第四季度登场

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 更多资源欢迎关注 6月22日消息&#xff0c;华为在HDC 2024上已经宣布&#xff0c;HarmonyOS NEXT开启开发者先锋用户Beta测试。 首批覆盖Mate 60系列、Mate X5系列、MatePad Pro 13.2英寸。 根据官方公布的时间表&…

oracle发送https请求

参照 https://docs.oracle.com/cd/E11882_01/appdev.112/e40758/u_http.htm#i1025869 https://docs.oracle.com/cd/E11882_01/network.112/e40393/asowalet.htm#ASOAG160 https://docs.oracle.com/cd/E11882_01/appdev.112/e40758/d_networkacl_adm.htm#ARPLS148 https://d…

江协科技51单片机学习- p11 Proteus安装模拟51单片机

前言&#xff1a; 本文是根据哔哩哔哩网站上“江协科技51单片机”视频的学习笔记&#xff0c;在这里会记录下江协科技51单片机开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了江协科技51单片机教学视频和链接中的内容。 引用&#xff1a; Proteus快速入门&…

OneNote for Windows 10 下载

OneNote for Windows 10 安装 1.在浏览器中输入地址&#xff1a;https://apps.microsoft.com/detail/9wzdncrfhvjl?hlzh-cn&glUS2OneNote for Windows 10 - 在 Windows 上免费下载并安装 |Microsoft StoreOneNote 是用于在设备上捕获和组织你的一切内容的数字笔记本。快速…