组合数取模
发布日期:2021-06-29 05:37:46
浏览次数:3
分类:技术文章
本文共 2651 字,大约阅读时间需要 8 分钟。
组合数取模就是求的值,当然根据,和的取值范围不同,采取的方法也不一样。
下面学习三种求法,参考大神
1、当和时,这个问题比较简单,组合数的计算可以靠杨辉三角,那么由于和的范围小,直接两层循环即可。
代码:
void getc(){ memset(C, 0, sizeof(C)); C[0][0] = 1; for(int i = 1; i < maxn; i++){ C[i][0] = 1; for(int j = 1; j < maxn; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod; }}2、 和 ,并且 是素数
采用Lucas定理
补充两个结论:
结论1. Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p);
结论2. 把n写成p进制a[n]a[n-1]a[n-2]...a[0],把m写成p进制b[n]b[n-1]b[n-2]...b[0],则C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余。
所以如果
那么得到
这样然后分别求,采用逆元计算即可。
求 ,其中 ,并且 是素数的代码:
#include#include #include using namespace std; typedef long long LL; LL n,m,p; LL quick_mod(LL a, LL b) { LL ans = 1; a %= p; while(b) { if(b & 1) { ans = ans * a % p; b--; } b >>= 1; a = a * a % p; } return ans; } LL C(LL n, LL m) { if(m > n) return 0; LL ans = 1; for(int i=1; i<=m; i++) { LL a = (n + i - m) % p; LL b = i % p; ans = ans * (a * quick_mod(b, p-2) % p) % p; } return ans; } LL Lucas(LL n, LL m) { if(m == 0) return 1; return C(n % p, m % p) * Lucas(n / p, m / p) % p; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%I64d%I64d%I64d", &n, &m, &p); printf("%I64d\n", Lucas(n,m)); } return 0; }
如果p比较小,可以打表处理n!(将上面的C()函数换成下面两个)
void init(){ fac[0]=1; for(int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;}ll C(ll n,ll m){ if(n3、 和 ,并且 可能为合数 对n和m分解质因数,然后用快速幂乘起来。
我们要求的是n!/(m! *(n-m)!),n!肯定可以整除(m! *(n-m)!),所以后面两个有的因子,n!都有,只要将它们因子的指数相加减,然后快速幂相乘取模即可。
代码:
#include其中work这个函数的作用是求出某个质因数的指数,比如将200!进行质因数分解,求里面有几个5: 假设n=200,那么因子5的个数=200/5+40/5+8/5=49,怎么得到的呢?200中5的倍数有40个,这40个数中其中是25的倍数的有8个,所以还能分解出8个5,这8个数中还有一个是125的倍数,还能分解出一个5,就这样一直循环下去,就能求出指数的值。#include #include using namespace std; typedef long long LL; const int N = 200005; bool prime[N]; int p[N]; int cnt; void isprime() { cnt = 0; memset(prime,true,sizeof(prime)); for(int i=2; i >= 1; a = a * a % m; } return ans; } LL Work(LL n,LL p) { LL ans = 0; while(n) { ans += n / p; n /= p; } return ans; } LL Solve(LL n,LL m,LL P) { LL ans = 1; for(int i=0; i >T; while(T--) { LL n,m,P; cin>>n>>m>>P; cout< <
(起初一直没明白work这个函数,看了这篇文章后豁然开朗,感谢)
另外还有 n,m≤10^9,p≤10^5可能是合数,与第3种相比n和m比较大,这种情况暂且不写了,可以参考这篇文章。
例题以后再补上。
转载地址:https://blog.csdn.net/zhj_fly/article/details/76293328 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月19日 13时40分57秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
现在做硬件工程师还有前途吗?
2019-04-29
用 50 种编程语言写“Hello,World!”
2019-04-29
GD32替换STM32,这些细节一定要知道。
2019-04-29
华为员工离职心声:菊厂15年退休,感恩,让我实现了财务自由!
2019-04-29
春晚上的“拓荒牛”
2019-04-29
嵌入式驱动自学者的亲身感受,有什么建议?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
腾讯机器狗,站起来了!
2019-04-29
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29
学会扶墙的机器人:没有什么能让我倒下!
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29
用单片机控制导弹?
2019-04-29
各种滤波器合集!
2019-04-29
国产CPU深度研究报告(干货,110页)
2019-04-29
在电路中,耦合是什么?有哪些方式?
2019-04-29