计算系数(NOIP2011提高LuoguP1313)

一道数论好题，知识点涉及扩展欧几里得，快速幂，逆元，二项式定理，模运算，组合数等。

（别问为啥打了快速幂不用费马小求逆元...我就练习下扩欧）

（数据就应该再加大些卡掉n^2递推求组合数的）

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int mod=10007;

void exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b==0)

	{

		x=1,y=0;

		return;

	}

	exgcd(b,a%b,x,y);

	ll t=x;

	x=y;

	y=t-a/b*y;

}

ll inv(ll a)

{

	ll x,y;

	exgcd(a,mod,x,y);

	return x;

}

ll fac(int x)

{

	ll ret=1;

	for(ll i=2;i<=x;++i)

		ret*=i,ret%=mod;

	return ret;

}

ll C(int a,int b)

{

	return (fac(a)*inv(fac(b)*fac(a-b))%mod+mod)%mod;

}

ll qpow(ll a,ll b)

{

	if(b==0)

		return 1;

	if(b==1)

		return a%mod;

	ll t=qpow(a,b>>1);

	t=(t*t)%mod;

	if(b&1)

		t=(t*a)%mod;

	return t;

}

int main()

{

	int a,b,k,n,m;

	scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);

	printf("%lld",(ll)((C(k,m)*qpow(a,n)%mod)*qpow(b,m)%mod+mod)%mod);

	return 0;

}

巴特西

计算系数(NOIP2011提高LuoguP1313)

最新文章

热门文章