当前位置：首页 > news >正文

求x的c(n,m)次方

news 来源：原创 2025/9/15 21:51:49

近期看到一类很有趣的题啊，其最基础的表现形式为求 $x^{\binom{n}{m}}$ mod P的值。

所以我们来拿一道小例题讲讲。

题面：给定 x,n,m，求： $x^{\binom{n}{m}}$ mod 1000003471的值。

首先我们注意到，题目给定的模数1000003471为质数，根据费马小定理， $x^{P-1}$ ≡ $x$ (mod P)。则只需求出 $\binom{n}{m}$ mod (P-1) 即可。

接下来我们将P-1做质因数拆分，得到其质因子{2,3,5,53,677,929}，那么我们可以套用中国剩余定理，将 $\binom{n}{m}$ mod (P-1) ≡ y拆解成数个形似 $\binom{n}{m}$ mod pi ≡ yi的方程，结合中国剩余定理便可得到原始方程。

在求yi的过程中，我们注意到其模数极小，所以无法套用阶乘与逆元的求组合数，我们需要使用到Lucas定理，其针对的便是求出组合数对于小质数取模的结果。

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int mod=1000003471;
inline ll qpow(ll x,ll y,int p){ll r=1;while(y){if(y&1) r=r*x%p;x=x*x%p;y>>=1;}return r;
}
ll inv[maxn],fac[maxn];
inline ll c(int n,int m,int p){if(n<m) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;
}
ll lucas(int n,int m,int p){if(!m) return 1;return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p;
}
inline ll getl(int n,int m,int p){fac[0]=1;for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;inv[p-1]=qpow(fac[p-1],p-2,p);for(int i=p-2;~i;i--) inv[i]=inv[i+1]*(i+1)%p;return lucas(n,m,p);
}
ll X,Y,G,lcm;
void exgcd(int a,int b){if(!b){X=1,Y=0,G=a;return;}exgcd(b,a%b);ll t=X;X=Y;Y=t-a/b*X;
}
void getxy(ll a,ll b,int c){exgcd(a,b);X*=c/G;lcm=a/G*b;b/=G;X=(X%b+b)%b;
}
pair<ll,ll> merge(ll a1,ll n1,ll a2,ll n2){getxy(n1,n2,a2-a1);return {(X*n1%lcm+a1)%lcm,lcm};
}
int a[7],b[7]={0,2,3,5,53,677,929},n,m,tot,x;
ll excrt(){pair<ll,ll> cur={0,1};for(int i=1;i<=tot;i++) cur=merge(cur.first,cur.second,a[i],b[i]);return cur.first;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);tot=6;cin>>x>>n>>m;for(int i=1;i<=tot;i++) a[i]=getl(n,m,b[i]);ll q=excrt();cout<<qpow(x,q,mod)<<endl;return 0;
}

接下来我们再看一道复杂一点的

P2480 [SDOI2010] 古代猪文

同样，简化题面，即为求出 $g^{\sum_{i=1}^{n}[i|n]*\binom{n}{i}}$ mod 999911659。

同样是套用上述方法，拆解出模数质因数为{2,3,4679,35617}。

在求对应yi是对于每个n的因数套用Lucas定理即可，注意特判。

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int mod=999911659;
const int b[]={0,2,3,4679,35617};
inline ll qpow(ll x,int y,int p){x%=mod;ll r=1;while(y){if(y&1) r=r*x%p;x=x*x%p;y>>=1;}return r;
} 
int n,g,m=4;
ll fac[maxn],inv[maxn],a[5];
inline ll c(int n,int m,int p){if(n<m) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;
}
ll lucas(int n,int m,int p){if(!m) return 1;return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p;
}
void so(int p,ll &ans){fac[0]=1;for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;inv[p-1]=qpow(fac[p-1],p-2,p);for(int i=p-2;~i;i--) inv[i]=inv[i+1]*(i+1)%p;for(ll i=1;i*i<=n;i++){if(n%i==0){ans+=lucas(n,i,p);if(n/i!=i) ans+=lucas(n,n/i,p);ans%=p;}}
}
ll X,Y,G,lcm;
void exgcd(int a,int b){if(!b){X=1,Y=0,G=a;return;}exgcd(b,a%b);ll t=X;X=Y;Y=t-a/b*Y;lcm=(ll)a/G*b;
}
void getxy(int a,int b,int c){exgcd(a,b);X*=c/G;b/=G;X=(X%b+b)%b;
}
pair<ll,ll> merge(int a1,int n1,int a2,int n2){getxy(n1,n2,a2-a1);return {(X*n1%lcm+a1)%lcm,lcm};
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>g;if(g%mod==0){cout<<0<<endl;return 0;}for(int i=1;i<=m;i++) so(b[i],a[i]);pair<ll,ll> cur={0,1};for(int i=1;i<=m;i++) cur=merge(cur.first,cur.second,a[i],b[i]);cout<<qpow(g,cur.first,mod)<<endl;return 0;
}
/*
2
3
4679
35617
*/

求x的c(n,m)次方

近期看到一类很有趣的题啊，其最基础的表现形式为求 mod P的值。所以我们来拿一道小例题讲讲。题面：给定 x,n,m，求： mod 1000003471的值。首先我们注意到，题目给定的模数1000003471为质数，根据费马…...

编程日记 2025/9/15 21:51:49

VS Code 的 .S 汇编文件里面的注释不显示绿色

1. 确认文件语言模式打开 .S 文件后，查看 VS Code 右下角的状态栏，确认当前文件的识别模式（如 Assembly、Plain Text 等）。如果显示为 Plain Text 或其他非汇编模式： 点击状态栏中的语言模式（如 Plain Te…...

编程日记 2025/9/11 3:25:53

Apipost自定义函数深度实战：灵活处理参数值秘籍

在开发过程中，为了更好地处理传递给接口的参数值，解决在调试过程中的数据处理问题，我们经常需要用到函数处理数据。过去，我们通过预执行脚本来处理数据，先添加脚本，然后将处理后的结果再赋值给请求参数。…...

编程日记 2025/9/8 9:34:43

ADI的BF561双核DSP怎么做开发，我来说一说（十）驱动直流电机和步进电机

作者的话 ADI的双核DSP，最早的一颗是Blackfin系列的BF561，这颗DSP我用了很久，比较熟悉，且写过一些给新手的教程。硬件准备 ADZS-BF561-EZKIT开发板：ADI原厂评估板 AD-ICE20000仿真器：ADI现阶段性能最好…...

编程日记 2025/9/13 7:45:14

JS包装类型Object

包装类型 1 对象 Object 声明普通对象学习静态方法，只能由Object自己调用 1.获得所有属性 2.获得所有属性值 3.对象拷贝...

编程日记 2025/8/17 19:41:44

【C++初阶】--- vector容器功能模拟实现

1.什么是vector？ 在 C 里，std::vector 是标准模板库（STL）提供的一个非常实用的容器类，它可以看作是动态数组 2.成员变量 iterator _start;：指向 vector 中第一个元素的指针。 iterator _finish;&#x…...

编程日记 2025/9/14 11:05:53

FreeRTOS项目工程完善指南：STM32F103C8T6系列

FreeRTOS项目工程完善指南：STM32系列本文是FreeRTOS STM32开发系列教程的一部分。我们将完善之前移植的FreeRTOS工程，添加串口功能并优化配置文件。更多优质资源，请访问我的GitHub仓库：https://github.com/Despacito0o/FreeRTO…...

编程日记 2025/9/8 17:24:51

多值字典表设计：优雅处理一对多关系的数据库方案

在数据库设计中，我们经常需要处理一对多的关系数据。传统做法是创建关联表，但有时这种方式会显得过于复杂。今天，我将分享一种简单而实用的多值字典表设计方案，它适用于那些不需要对单个值进行复杂操作的场景。为什么需要多值字典表？在许多应用场景中，我们需要存储一…...

编程日记 2025/9/13 22:38:02

如何在Linux系统Docker部署Dashy并远程访问内网服务界面

## 简介 Dashy 是一个开源的自托管的导航页配置服务，具有易于使用的可视化编辑器、状态检查、小工具和主题等功能。你可以将自己常用的一些网站聚合起来放在一起，形成自己的导航页。一款功能超强大，颜值爆表的可定制专属导航页工…...

编程日记 2025/9/15 11:15:58

GRBL运动控制算法（五）脉冲生成Bresenham算法

前言在数控系统和运动控制领域，脉冲信号的精确生成是实现高精度位置控制的核心。GRBL作为一款高效、开源的嵌入式运动控制固件，其底层脉冲生成机制直接决定了步进电机的运动平滑性、响应速度及整体性能。而这一机制的核心，正是经典的Bresen…...

编程日记 2025/9/15 20:03:21

Java学习手册：Java发展历史与版本特性

Java作为全球最流行的编程语言之一，其发展历程不仅见证了技术的演进，也反映了软件开发模式的变革。从1995年的首次发布到如今的持续更新，Java始终保持着强大的生命力和广泛的影响力。本文将简要回顾Java的发展历程，并重点介绍其关…...

编程日记 2025/9/10 19:39:32

25年时代电服社招入职Verify测评SHL题库语言理解数字推理考什么？

宁德时代语言理解语言理解部分主要考察应聘者的语言表达和逻辑思维能力，题型包括阅读理解、逻辑填空和语句排序。阅读理解要求应聘者快速捕捉文章的主旨和细节信息，能够迅速把握文章的核心观点；逻辑填空需要在给定的语句中填入最合适的词汇…...

编程日记 2025/9/8 19:51:11

【C++】右值引用、移动语义与完美转发

左值、右值是C常见的概念，那么什么是右值引用，移动语义，完美转发呢？本UP带大家了解一下C校招常问的C11新特性。左值与右值左值：明确存储未知、可以取地址的表达式右值：临时的、即将被销毁的&#xff…...

编程日记 2025/9/13 3:04:02

AIGC3——AIGC的行业应用与生产力变革：医疗、教育、影视与工业设计的突破

引言人工智能生成内容（AIGC）技术正在深刻改变多个行业的生产方式，从医疗诊断到影视创作，从个性化教育到工业设计，其应用不仅提升了效率，还创造了全新的工作模式。本文将聚焦医疗、教育、影视、工业设计四…...

编程日记 2025/9/15 12:05:51

Java从入门到“放弃”（精通）之旅——启航①

🌟Java从入门到“放弃 ”精通之旅🚀 今天我将要带大家一起探索神奇的Java世界！希望能帮助到同样初学Java的你~ (๑•̀ㅂ•́)و✧ 🔥 Java是什么？为什么这么火？ Java不仅仅是一门编程语言，更…...

编程日记 2025/9/4 0:40:51

Web前端之Vue+Element实现表格动态不同列合并多行、localeCompare、forEach、table、push、sort、Map

MENU 效果图公共数据数据未排序时（需要合并的行数据未处于相邻位置）固定合并行（写死）动态合并行方法（函数）执行效果图公共数据 Html <el-table :data"tableData" :span-method"chang…...

编程日记 2025/9/10 6:19:11

JavaScript（JS进阶）

目录 00闭包 01函数进阶 02解构赋值 03通过forEach方法遍历数组 04深入对象 05内置构造函数 06原型 00闭包 <html><body><script>// 定义：闭包内层函数（匿名函数）外层函数的变量（s&…...

编程日记 2025/9/9 3:22:09

学习51单片机Day02---实验：点亮一个LED灯

目录 1.先看原理图 2.思考一下（sbit的使用）： 3.给0是要让这个LED亮（LED端口设置为低电平） 4.完成的代码 1.先看原理图比如我们要让LED3亮起来，对应的是P2^2。 2.思考一下（sbit的使用&…...

编程日记 2025/9/11 15:09:57

#利用线性回归模型california房价预测 #调用API from sklearn.datasets import fetch_california_housing from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler from sklearn.linear_model import LinearRegression,SGDRe…...

编程日记 2025/9/12 21:56:47

c++进阶之----异常

1. 异常处理的基本概念异常处理是 C 中一种用于处理运行时错误的机制，允许程序在遇到错误时优雅地处理问题，而不是直接崩溃。异常处理的核心是通过 try、catch 和 throw 关键字来实现，它允许程序在遇到错误时优雅地处理问题，而不…...

编程日记 2025/9/14 18:49:11

SmolDocling：一种超紧凑的视觉语言模型，用于端到端多模态文档转换

paper地址：SmolDocling: An ultra-compact vision-language model for end-to-end multi-modal document conversion Huggingface地址：SmolDocling-256M-preview 代码对应的权重文件：SmolDocling-256M-preview权重文件一、摘要以下是文章摘要的总结： SmolDocling 是一…...

编程日记 2025/9/13 17:27:07

多模态大模型在目标检测领域的最新进展

1. 技术融合创新多模态数据融合： 传感器融合：整合图像、激光雷达（LiDAR）、毫米波雷达等数据，提升检测精度和鲁棒性。例如，在自动驾驶中，通过融合视觉与LiDAR数据，实现三维目标检测…...

编程日记 2025/9/5 7:02:02

KWDB创作者计划—KWDB技术重构：重新定义数据与知识的神经符号革命

引言：数据洪流中的范式危机在AI算力突破千卡集群、大模型参数量级迈向万亿的时代，传统数据库系统正面临前所未有的范式危机。当GPT-4展现出跨领域推理能力，AlphaFold3突破蛋白质预测精度时，数据存储系统却仍在沿用基于关系代数的…...

编程日记 2025/9/6 12:58:18

我开源了一个“宝藏”开源项目

我开源了一个“宝藏”开源项目 - AI需求分析项目 | 适合交作业和学习 🚀 前言大家好！最近在学习软件工程和大模型应用开发的过程中，我发现许多学生都遇到了需求分析AI的题目。把一份需求文档转化为用户故事、实体关系或数据库设计&#xff…...

编程日记 2025/9/10 19:55:50

从零实现Agent智能体配置使用（Ragflow）

从零实现Agent智能体配置使用（Ragflow） 1. 创建智能体2. 配置智能体2.1 配置问题识别2.2 配置问题分类2.3 不同问题进行单独配置2.4 保存Agent 3. 体验效果 1. 创建智能体 2. 配置智能体 2.1 配置问题识别 2.2 配置问题分类 2.3 不同问题进行单独配置当…...

编程日记 2025/9/10 3:03:09

Fluent VOF水下固体火箭发射仿真

本案例利用VOF模型对水下固体火箭（10m水深）发动机点火初期的流场进行了仿真。该案例所用模型为假设模型，且缺少相关燃气参数，仅作计算设置参考。通过此案例后续跨可以对不同水深、不同模型的工况展开类似仿真计算。 1 假设说明 …...

编程日记 2025/9/11 16:08:03

电脑死机/锁屏后死机无法唤醒

电脑死机/锁屏后死机无法唤醒导航文章目录电脑死机/锁屏后死机无法唤醒导航一、系统日志分析二、电源管理与睡眠模式问题1、禁用快速启动2、调整电源计划（开启高性能模式&关闭硬盘休眠）若是没有禁用睡眠和关闭显示器方法一：方法二&am…...

编程日记 2025/9/7 21:00:52

爱普生可编程晶振SG8201CJ和SG8200CJ在胃镜机器人发挥重要作用

在医疗机器人技术高速发展的今天，胃镜机器人作为胃肠道疾病诊断与治疗的创新设备，正逐渐改变传统诊疗模式。其复杂精密的系统需要精准的时间同步与稳定的信号输出，胃镜机器人是一种先进的医疗设备，用于无创性地检查胃部疾病。与传…...

编程日记 2025/9/8 20:10:10

按规则批量修改文件名称，支持替换或删除文件名称中的内容

文件重命名的需求在我们工作中是非常常见的一个需求，也非常的重要的一个需求，我相信很多小伙伴在工作中都会碰到需要进行文件重命名的场景。今天就给大家介绍一个文件重命名的方法，支持多种方式批量修改文件名称。功能非常的强大，…...

编程日记 2025/9/14 1:31:21

scrum详细理解

Scrum与传统瀑布模型区别瀑布模型：需要花费几个月来规划产品----->在花费几个月时间进行研发----->产品测试、评审----->最终发布产品缺点：①如果市场需求发生变化，研发的产品可能无法满足市场需求 ②产品规划必须早于后续工作之…...

编程日记 2025/9/11 3:23:23

数据结构（五)——AVL树（平衡二叉搜索树)

目录前言 AVL树概念 AVL树的定义 AVL树的插入右旋转左旋转左右双旋右左双旋插入代码如下所示 AVL树的查找 AVL树的遍历 AVL树的节点个数以及高度判断平衡 AVL树代码如下所示小结前言前面我们在数据结构中介绍了二叉搜索树，其中提到了二叉搜…...

编程日记 2025/9/8 16:27:06

Linux文件传输：让数据飞起来！

一、前置任务为了便于实验，我用母盘的虚拟机克隆出两台虚拟机来模拟两台主机进行文件传输查询两台主机的IP BL1 192.168.163.130/24 BL2 192.168.88.129/24 二、文件传输 scp命令不填选项正常显示进度的传输-q静默传输-r递归传输（用于传输目录及目…...

编程日记 2025/9/12 4:15:10

repo仓库文件清理

1. repo 仓库内文件清理 # 清理所有Git仓库中的项目 repo forall -c git clean -dfx # 重置所有Git 仓库中的项目 repo forall -c git reset --hard 解释： repo forall -c git clean -dfx： repo forall 是一个用于在所有项目中执行命令的工具。-c 后…...

编程日记 2025/9/9 7:52:40

MyBatis-Plus 的 FieldStrategy 属性

前几天做个需求的时候，有几个字段在更新的时候，可能为空。想着MyBatis-Plus有注解可以直接使用，就找寻了一下。此处记录一下。我用的MyBatis-Plus的版本是 3.5.1。版本之间对于 TableField 中的方法定义有些区别，但大体相差不大。…...

编程日记 2025/9/11 18:30:05

解锁塔能科技，开启工厂绿色转型与可持续发展双引擎

在全球积极推进可持续发展的大背景下，能源的高效利用与节能减排，已成为各行各业迈向高质量发展进程中无法回避的核心任务。工厂作为能源消耗大户与污染排放重点源头，其绿色转型迫在眉睫，这不仅关乎企业自身的长远发展，…...

编程日记 2025/9/9 21:16:42

c++进阶--智能指针

大家好，今天我们来学习一下c中的智能指针部分。智能指针的使⽤及其原理 1. 智能指针的使⽤场景分析下⾯程序中我们可以看到，new了以后，我们也delete了，但是因为抛异常导，后⾯的delete没有得到执⾏，所以…...

编程日记 2025/9/13 22:14:48

五种常用的web加密算法

文章目录五种常用Web加密算法实战及原理详解1. AES (高级加密标准)原理详解应用场景实战代码（Node.js） 2. RSA (非对称加密)原理详解应用场景实战代码（Node.js） 3. SHA-256 (安全哈希算法)原理详解应用场景实战代码（浏…...

编程日记 2025/9/11 11:02:54

LeetCode 题目「二叉树的右视图」中，如何从「中间存储」到「一步到位」实现代码的优化？

背景简介在 LeetCode 的经典题目「二叉树的右视图」中，我们需要返回从右侧看一棵二叉树时所能看到的节点集合。每一层我们只能看到最右边的那个节点。最初，我采用了一个常规思路：层序遍历每层单独保存节点值最后提取每层最后一个节…...

编程日记 2025/9/7 5:00:21

MySQL——存储过程、索引

一、存储过程 1、存储过程使用的场景例如：有一个购物网站，要验证查询商品的性能，测试之前肯定要准备大量的测试数据，如果是通过执行 insert 语句一条一条进行插入，效率很低。这种情况下，写一个存储过程…...

编程日记 2025/9/12 21:59:40

【项目管理】第9章项目范围管理

相关文档，希望互相学习，共同进步风123456789～-CSDN博客（一）知识总览项目管理知识域知识点：（项目管理概论、立项管理、十大知识域、配置与变更管理、绩效域）对应：第6章-第19章（二）知识笔记第9章项目范围管理 1.管理基础 1.1 产品范围…...

编程日记 2025/9/9 6:49:10

无人机隐身技术难点要点！

全频段雷达隐身频段覆盖挑战：传统隐身材料（如铁氧体、掺杂半导体）多针对特定频段（如X波段），难以应对米波至毫米波的宽频段探测。低频段突破：低频雷达（如米波雷达）波长…...

编程日记 2025/9/10 11:41:18

gerrit配置及使用git-lfs

gerrit服务器端配置下载git-lfs插件登录Dashboard [Jenkins] (gerritforge.com)，下载对应版本的插件配置gerrit 将下载的lfs.jar插件放到${GERRIT_SITE}/plugins/下面为所有仓库启用git-lfs 此步骤需要修改 All-projects 仓库配置，步骤如下 1、克隆仓…...

编程日记 2025/9/13 14:20:28

基于DNS的负载均衡和反向代理负载均衡

基于 DNS 的负载均衡和反向代理负载均衡有一些相似之处，但实际上它们存在诸多区别，主要体现在以下几个方面： 工作原理 DNS 负载均衡：通过在 DNS 服务器中为同一主机名配置多个 IP 地址，DNS 服务器根据一定的算法&…...

编程日记 2025/9/11 3:01:03

Windows10 ssh无输出 sshd服务启动失败 1067报错公钥无法认证链接解决办法

背景描述最近突然发现windows 10的ssh服务好像挂了，在系统设置-可选功能那里反复重新安装还是报错。命令行输入ssh按回车无输出（正常情况下应该输出一堆参数说明），但是Get-Command ssh 又可以找到system32下的ssh程序。任务管理…...

编程日记 2025/9/12 6:50:13

【图书管理系统】深入解析基于 MyBatis 数据持久化操作：全栈开发图书管理系统：查询图书属性接口（注解实现）、修改图书属性接口（XML 实现）

查询图书属性接口约定前后端交互接口约定前后端交互接口，进入修改页面，需要显示当前图书的信息； 请求 /book/queryBookById?bookId25 参数无响应 { "id": 25, "bookName": "图书21", "…...

编程日记 2025/9/12 1:00:15

消息队列（IPC技术）

目录一、Linux 中主要的进程间通信方式如下： 二、消息队列函数 （1）msgget函数功能概述函数原型参数解释返回值示例结果问题 (2) msgsnd函数功能概述函数原型参数说明返回值示例结果 （3&#xff0…...

编程日记 2025/9/3 7:08:43

分支语句和循环语句

什么是语句？ C语言中由一个分号;隔开的就是一条语句。比如： printf("haha");12;分支语句 if语句 if语句的语法结构: if(表达式)语句;if(表达式)语句1; else语句2;//多分支 if(表达式1)语句1; else if(表达式2)语句2; else语句3;在C语言…...

编程日记 2025/9/15 10:47:17