链接：https://ac.nowcoder.com/acm/contest/4381/B

题目描述 

    牛牛并不是一个擅长组合数学的选手,但是这并不妨碍他喜欢做组合数学。虽然他人是菜,但是他嘴巴不菜。

    众所周知,计算组合数C_i^jCij​是组合数学中最简单的事情.现在牛牛遇到了一个难题,给出n,m,pn,m,p,他想知道C_n^mCnm​是否等于pp。

输入描述:

一行三个数分别代表n,m,pn,m,p.

输出描述:

如果C_n^m = pCnm​=p,输出Yes!Yes!.否则输出No!No!

示例1

输入

复制

4 2 6

输出

复制

Yes!

备注:


 

1 \leq n \leq 1e91≤n≤1e9

0 \leq m \leq \min(1e5, n)0≤m≤min(1e5,n)

1 \leq p \leq 10^{4e5}1≤p≤104e5

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int quick_power_mod(int a,int b,int m)
{
	int result = 1;
	int base = a;
	while(b>0)
	{
		if(b&1==1)
		result=(result*base)%m;
		base=(base*base)%m;
		b>>=1;
	}
	return result;
}
ll comp(ll a,ll b,int p)
{
	if(a<b)return 0;
	if(a==b)return 1;
	if(b>a-b)b=a-b;
	int ans=1,ca=1,cb=1;
	for(ll i=0;i<b;i++)
	{
		ca=(ca*(a-i))%p;
		cb=(cb*(b-i))%p;
	}
	ans=(ca*quick_power_mod(cb,p-2,p))%p;
	return ans;
}
ll lucas(ll n,ll m,ll p)
{
	ll ans=1;
	while(n&&m&&ans)
	{
		ans=(ans*comp(n%p,m%p,p))%p;
		n/=p;
		m/=p;
	}
	return ans;
}
char str[1000001];
int main()
{
	ll m,n;
	scanf("%lld %lld %s",&n,&m,str);
	ll ans=0,s;
	s=strlen(str);
	ll mod=10007;
	for(int i=0;i<s;i++)
	{
        ans=ans*10+str[i]-'0';
        ans%=mod;
    }
	if(lucas(n,m,10007)==ans)
	cout<<"Yes!"<<endl;
	else
	cout<<"No!"<<endl;
	return 0;
}