【bzoj2982】combination Lucas定理
定理 combination
2023-09-11 14:22:40 时间
原文地址:http://www.cnblogs.com/GXZlegend/p/6801490.html
题目描述
LMZ有n个不同的基友,他每天晚上要选m个进行[河蟹],而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢?当然,LMZ的一年有10007天,所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)
输入
第一行一个整数t,表示有t组数据。(t<=200)
接下来t行每行两个整数n, m,如题意。
输出
T行,每行一个数,为C(n, m) mod 10007的答案。
样例输入
4
5 1
5 2
7 3
4 2
样例输出
5
10
35
6
题解
Lucas定理:C(n , m) mod p = C(n/p , m/p) * C(n mod p , m mod p) mod p(p为质数)
然后快速幂求个逆元就没啥了。
#include <cstdio> #define mod 10007 int fac[10010]; int pow(int x , int y) { int ans = 1; while(y) { if(y & 1) ans = ans * x % mod; x = x * x % mod , y >>= 1; } return ans; } int cal(int n , int m) { if(n < m) return 0; return fac[n] * pow(fac[m] , mod - 2) % mod * pow(fac[n - m] , mod - 2) % mod; } int lucas(int n , int m) { if(!m) return 1; return cal(n % mod , m % mod) * lucas(n / mod , m / mod) % mod; } int main() { int t , n , m , i; scanf("%d" , &t); fac[0] = 1; for(i = 1 ; i < mod ; i ++ ) fac[i] = fac[i - 1] * i % mod; while(t -- ) { scanf("%d%d" , &n , &m); printf("%d\n" , lucas(n , m)); } return 0; }
相关文章
- 【LOJ#6485】LJJ 学二项式定理(单位根反演)
- 【BZOJ3129】[SDOI2013]方程(容斥,拓展卢卡斯定理)
- 中国剩余定理 CRT
- 【BZOJ5297】【CQOI2018】社交网络(矩阵树定理)
- 【SPOJ】Highways(矩阵树定理)
- UVa 10294 Arif in Dhaka (First Love Part 2) (Polya定理)
- POJ 1006 Biorhythms (中国剩余定理)
- HDU 3944 DP? (Lucas定理)
- 高数 | 积分中值定理的开闭区间、积分第一中值定理及其推广
- 洛谷 P3807 【模板】卢卡斯定理
- 神经网络的万能近似定理
- 中国剩余定理具体解释
- POJ 1006 Biorhythms (数论-中国剩余定理)
- 【bzoj4894】天赋 矩阵树定理
- 【bzoj4403】序列统计 Lucas定理
- 同余定理