[CRT][中国剩余定理]膜法

2024-02-24 03:20
文章标签 中国 定理 crt 剩余 膜法

本文主要是介绍[CRT][中国剩余定理]膜法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这里写图片描述

容易发现是杨辉三角形,第i个数的贡献为c(n-1,i-1);但是由于mod数不是质数,所以考虑用CRT来做。先拆mod数,然后在求组合数的过程中将每个数拆成a*pi^ci的形式,非常感谢dmsdalao对我中国剩余定理的指导。
关于CRT详见
http://blog.csdn.net/qq_36993218/article/details/60956475


#include<cstdio>
#include<algorithm>
#include<iostream>
#define ll long long
#define Pair pair<ll,ll>
using namespace std;
int n,K;
inline int read()
{char c;bool flag=false;while((c=getchar())>'9'||c<'0')if(c=='-') flag=true;int res=c-'0';while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';return flag?-res:res;
}
const int N=4*1e5+7;
int tot,a[N];
ll p[N],c[N],m[N],M[N],H[N],ans[N];
inline ll ksm(ll a,int b)
{ll res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;
}
inline ll ksm(ll a,int b,int pyz)
{ll res=1;while(b){if(b&1) res=res*a%pyz;a=a*a%pyz;b>>=1;}return res;
}
inline ll inv(ll a,int x)
{return ksm(a,(p[x]-1)*m[x]/p[x]-1,m[x]);
}
Pair fac[N];
inline Pair div(Pair A,Pair B,int x)
{return Pair(A.first*inv(B.first,x)%m[x],A.second-B.second);
}
inline Pair mul(Pair A,Pair B,int x)
{return Pair(A.first*B.first%m[x],A.second+B.second);
}
inline Pair C(int n,int m,int x)
{return div(fac[n],mul(fac[m],fac[n-m],x),x);
}
inline Pair trans(int i,int x)
{Pair res=Pair(0,0);while(i%p[x]==0&&i){i/=p[x];res.second++;} res.first=i;return res;
}
inline ll get_num(Pair x,int i)
{return (ll)x.first*ksm(p[i],x.second,m[i])%m[i];
} 
inline void solve(int now)
{fac[0]=Pair(1,0);for(int i=1;i<=n;++i)fac[i]=mul(fac[i-1],trans(i,now),now);for(int i=1;i<=n;++i)ans[now]=(ans[now]+get_num(mul(trans(a[i],now),C(n-1,i-1,now),now),now))%m[now];
} 
int main()
{freopen("magic.in","r",stdin);freopen("magic.out","w",stdout);n=read();K=read();for(int i=1;i<=n;++i) a[i]=read();int tmp=K;for(int i=2;i<=tmp;++i)if(tmp%i==0){p[++tot]=i;while(tmp%i==0){c[tot]++;tmp/=i;}}for(int i=1;i<=tot;++i){m[i]=ksm(p[i],c[i]);M[i]=K/m[i];H[i]=inv(M[i],i);solve(i);}ll Ans=0;for(int i=1;i<=tot;++i)Ans=(Ans+(ll)ans[i]*M[i]%K*H[i]%K)%K;cout<<Ans; 
}

这篇关于[CRT][中国剩余定理]膜法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/740793

相关文章

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展

【科技明说 | 科技热点关注】 2024戴尔科技峰会在8月如期举行,虽然因事未能抵达现场参加,我只是观看了网上在线直播,也未能采访到DTF现场重要与会者,但是通过数十年对戴尔的跟踪与观察,我觉得2024戴尔科技峰会给业界传递了6大重要信号。不妨简单聊聊:从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展? 1)退出中国的谣言不攻自破。 之前有不良媒体宣扬戴尔将退出中国的谣言,随着2

Java验证辛钦大数定理

本实验通过程序模拟采集大量的样本数据来验证辛钦大数定理。   实验环境: 本实验采用Java语言编程,开发环境为Eclipse,图像生成使用JFreeChart类。   一,验证辛钦大数定理 由辛钦大数定理描述为: 辛钦大数定理(弱大数定理)  设随机变量序列 X1, X2, … 相互独立,服从同一分布,具有数学期望E(Xi) = μ, i = 1, 2, …, 则对于任意正数ε ,

【中国国际航空-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 1. 暴力破解密码,造成用户信息泄露 2. 短信盗刷的安全问题,影响业务及导致用户投诉 3. 带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 所以大部分网站及App 都采取图形验证码或滑动验证码等交互解决方案, 但在机器学习能力提高的当下,连百度这样的大厂都遭受攻击导致点名批评, 图形验证及交互验证方式的安全性到底如

CPC23三 K.(Lucas定理)

K.喵喵的神·数 Time Limit: 1 Sec Memory Limit: 128 MB Description 喵喵对组合数比较感兴趣,并且对计算组合数非常在行。同时为了追求有后宫的素质的生活,喵喵每天都要研究质数。 我们先来复习一下什么叫做组合数。对于正整数P、T 然后我们再来复习一下什么叫质数。质数就是素数,如果说正整数N的约数只有1和它本身,N

中国书法——孙溟㠭浅析碑帖《越州石氏帖》

孙溟㠭浅析碑帖《越州石氏帖》 《越州石氏帖》  是一部汇集多本摹刻的帖,南宋时期的会稽石邦哲(字熙明)把家藏的一些法书碑帖集中一起摹刻成的,宋理宗时临安书商陈思《宝刻丛编》有记載这部帖的目录。现在还存有宋代时拓的残缺本,大多是相传的晋朝唐朝的小楷,后人多有临摹学习,并以此版本重新摹刻。 (图片来源于网络) 图文/氿波整理

将中国标准时间转换为年月日时分秒格式

1.将中国标准时间转换为年月日时分秒格式 代码如下(示例): // 时间格式化timestampToTime(timestamp) {var chinaStandard=Mon Jul 19 2021 11:11:55 GMT+0800 (中国标准时间);var date = new Date(chinaStandard);var y = date.getFullYear();var m =

热烈庆祝中国科学技术大学建校六六周年

卡西莫多的诗文集2022-2024.9月6-校庆国庆专版   欢迎分享 通过网盘分享的文件:卡西莫多的诗文集2022-2024.9月6-A5-校庆国庆专版.pdf 链接:  百度网盘 请输入提取码 提取码: umpm

《中国全屋智能行业发展现状与投资前景研究分析报告》

报告导读:本报告从国际全屋智能发展、国内全屋智能政策环境及发展、研发动态、供需情况、重点生产企业、存在的问题及对策等多方面多角度阐述了全屋智能市场的发展,并在此基础上对全屋智能的发展前景做出了科学的预测,最后对全屋智能投资潜力进行了分析。  订购链接:https://www.yxresearch.com/ 第一章全屋智能行业概念界定及发展环境剖析 第一节全屋智能行业相关概念界定 一、智能家