【BZOJ】2982: combination(lucas定理+乘法逆元)
http://www.lydsy.com/JudgeOnline/problem.php?id=2982
少加了特判n<m return 0就wa了QAQ
lucas定理:C(n, m)%p=(C(n%p, m%p)*C(n/p, m/p))%p
等英语好一点去wiki看一下证明吧QAQhttp://en.wikipedia.org/wiki/Lucas%27_theorem
然后这是网上搜到的关于lucas的一些内容
首先给出这个Lucas定理:
A、B是非负整数,p是质数。AB写成p进制:A=a[n]a[n-1]...a[0],B=b[n]b[n-1]...b[0]。则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) mod p同余
即:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)
这个定理的证明不是很简单,我一直想找个很好的张明,但是,没找到,昨天看到了一个解题报告,基本上可以说明白这个Lucas定理是怎么回事了,具体的是说:
以求解n! % p为例,把n分段,每p个一段,每一段求的结果是一样的。但是需要单独处理每一段的末尾p, 2p, ...,把p提取出来,会发现剩下的数正好又是(n / p)!,相当于划归成了一个子问题,这样递归求解即可。
这个是单独处理n!的情况,当然C(n,m)就是n!/(m!*(n-m)!),每一个阶乘都用上面的方法处理的话,就是Lucas定理了,注意这儿的p是素数是有必要的。
Lucas最大的数据处理能力是p在10^5左右,不能再大了,hdu 3037就是10^5级别的!
对于大组合数取模,n,m不大于10^5的话,用逆元的方法,可以解决。对于n,m大于10^5的话,那么要求p<10^5,这样就是Lucas定理了,将n,m转化到10^5以内解。
然后左边暴力加逆元就行了,右边就是lucas。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int MD=10007;
int mpow(int a, int b) {
int ret=1;
for(; b; b>>=1, a=(a*a)%MD) if(b&1) ret=(ret*a)%MD;
return ret;
}
int getc(int n, int m) {
if(n<m) return 0;
int up=1, down=1;
for1(i, m+1, n) up=(up*i)%MD;
for1(i, 1, n-m) down=(down*i)%MD;
return (up*mpow(down, MD-2))%MD;
}
int lucas(int n, int m) {
return m?(getc(n%MD, m%MD)*lucas(n/MD, m/MD))%MD:1;
} int main() {
int t=getint();
while(t--) {
int n=getint(), m=getint();
printf("%d\n", lucas(n, m));
}
return 0;
}
Description
Input
Output
Sample Input
5 1
5 2
7 3
4 2
Sample Output
10
35
6
HINT
Source
最新文章
- 基于Metronic的Bootstrap开发框架经验总结(11)--页面菜单的几种呈现方式
- Verilog笔记——YUV2RGB的模块测试
- 主流浏览器css兼容问题的总结
- 分模块的maven项目调试时报Source not found的解决办法
- ES6中的Class
- something about english
- 爆破vcrkme01(已补上注册机)
- scjp考试准备 - 5 - 重载和重写
- Ambari源代码分析之总览
- IIS与ASP.NET中的队列
- 端口扫描器之java实现
- ora-01653: unable to extend table sys.aud$ by 8192 in tablespac system[转载]
- div+css位置绝对定位和相对定位
- Hive笔记——技术点汇总
- Windows环境下多线程编程原理与应用读书笔记(8)————信号量及其应用
- 创建vs离线安装程序(不联网安装vs)
- java HttpClient 忽略证书的信任的实现 MySSLProtocolSocketFactory
- java 判断null和空
- 每天学习一个Linux命令-目录
- linux上安装redis4.0.9