洛谷P3807 卢卡斯定理

题目背景

这是一道模板题。

题目描述

给定n,m,p(1\le n,m,p\le 10^51≤n,m,p≤10
5
)

求 C_{n+m}^{m}\ mod\ pC
n+m
m
​ mod p
保证P为prime

C表示组合数。

一个测试点内包含多组数据。

输入输出格式

输入格式：
第一行一个整数T(T\le 10T≤10)，表示数据组数

第二行开始共T行，每行三个数n m p，意义如上

输出格式：
共T行，每行一个整数表示答案。

输入输出样例

输入样例#1：
2
1 2 5
2 1 5
输出样例#1：
3
3

---

懒得使用makedown了(懒癌晚期)

---

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define maxn 100010
#define int long long
using namespace std ;
int a[maxn] , p ,T,n,m;
int quick_power(int x , int p , int mod ) ;
int C(int n , int m) ;
int lucas(int n , int m) ;
int read() ;
signed main() {
	T = read() ;
	while(T --) {
		n = read() , m = read() , p = read() ;
		a[0] = 1 ;
		for(int i = 1 ; i <= p ; i ++ ) {
			a[i] = (a[i-1]*i)%p ;
		}
		cout << lucas(n+m,m) << endl ;
	}
	return 0 ;
} 
int read() {
	int x = 0 , f = 1 ;char s = getchar() ;
	while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
	return x*f ;
}
int lucas(int n , int m ) {
	if(!m) return 1 ;
	return C(n%p,m%p)*lucas(n/p,m/p)%p ;
}
int C(int n , int m ) {
	if(m>n) return 0 ;
	return ((a[n]*quick_power(a[m],p-2,p))%p*quick_power(a[n-m],p-2,p)%p) ;
}
int quick_power(int x , int p , int mod) {
	int res = 1 ;
	x %= mod ;
	for(;p;p>>=1,x=x*x%mod) {
		if(p&1) res = res*x%mod ; 
	}
	return res ;
}

十分奇怪的码风有木有?

完结散花