欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战NOIP——模板复习6

程序员文章站 2022-03-23 10:57:55
...

这里只有模板,并不作讲解,仅为路过的各位做一个参考以及用做自己复习的资料,转载注明出处。

卢卡斯定理

/*Copyright: Copyright (c) 2018
*Created on 2018-10-28  
*Author: 十甫
*Version 1.0 
*Title: Lucas
*Time: inf mins
*/ 
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int size = 100005;

ll a, b, p, inv[size], factor[size];
ll Lucas(ll x, ll y) {
	if(x < y) return 0;
	else if(x < p) return factor[x] * inv[y] * inv[x - y] % p;
	else return Lucas(x / p, y / p) * Lucas(x % p, y % p) % p;
}
int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld%lld", &a, &b, &p);
		inv[0] = inv[1] = 1;
		for(int i = 2;i <= a + b;i++) {
			inv[i] = inv[p % i] * (p - p / i) % p;
		}
		for(int i = 2;i <= a + b;i++) {
			inv[i] = inv[i - 1] * inv[i] % p;
		}
		factor[0] = factor[1] = 1;
		for(int i = 2;i <= a + b;i++) {
			factor[i] = factor[i - 1] * i % p;
		}
		printf("%lld\n", Lucas(a + b, b));
	}
	return 0;
}

 

相关标签: 数论 组合数学