【Luogu3807】【模板】卢卡斯定理（数论）

题目描述

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

求 \(C_{n+m}^m mod p\)

保证\(P\)为\(prime\)

\(C\)表示组合数。

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

输入输出格式

输入格式：

第一行一个整数\(T(T≤10)\)，表示数据组数

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

输出格式：

共\(T\)行，每行一个整数表示答案。

输入输出样例

输入样例#1：

2

1 2 5

2 1 5

输出样例#1：

3

3

题解

卢卡斯定理模板题

卢卡斯定理：

\(C_{m}^{n}≡C_{m/p}^{n/p}*C_{m\%p}^{n\%p}(mod p)\)

当\(n,m\)很大，而\(P\)很小的使用

递归计算即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

ll n,m,P;

ll jc[100100];

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

ll Pow(ll a,ll b)

{

	ll s=1;

	while(b)

	{

		if(b&1)s=1ll*s*a%P;

		a=a*1ll*a%P;

		b>>=1;

	}

	return s;

}

ll C(ll n,ll m)

{

	if(m>n)return 0;

	return jc[n]*Pow(jc[m]*jc[n-m]%P,P-2)%P;

}

ll Lucas(ll n,ll m)

{

	if(m==0)return 1;

	return (Lucas(n/P,m/P)*C(n%P,m%P))%P;

}

int main()

{

	int T=read();

	while(T--)

	{

		jc[0]=1;

		n=read();m=read();P=read();

		for(int i=1;i<=P;++i)jc[i]=jc[i-1]*1ll*i%P;

		printf("%lld\n",Lucas(n+m,m)%P);

	}

	return 0;

}