【51nod】 1119

1119 機器人走方格 V2

基準時間限制：1 秒 空間限制：131072 KB 分值: 10  難度：2級算法題

 收藏

 關注 M * N的方格，一個機器人從左上走到右下，隻能向右或向下走。有多少種不同的走法？由于方法數量可能很大，隻需要輸出Mod 10^9 + 7的結果。 Input

第1行，2個數M,N，中間用空格隔開。（2 <= m,n <= 1000000)      

Output

輸出走法的數量 Mod 10^9 + 7。      

Input示例

2 3      

Output示例

3      

代碼：

#include<cstdio>
#define LL long long
LL mod=1e9+7;
LL fac[2000000+5]={1,1};  //不能是1000000+5，因為C(m+n-2,m-1),求階乘的時候注意m+n-2的範圍 
void getfac()
{
	for(int i=2;i<=2000000;i++)
		fac[i]=fac[i-1]*i%mod;
}
LL quickmod(LL a,LL b)
{
	LL ans=1;	
	while(b!=0)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ans;
}
LL C(LL n,LL k)
{
	if(n<k)
		return 0;
	return 	((fac[n]%mod)*quickmod(fac[k]*fac[n-k]%mod,mod-2)%mod)%mod;
}
LL lucas(LL n,LL k)
{
	if(k==0)
		return 1;
	return (C(n%mod,k%mod)*lucas(n/mod,k/mod))%mod;	
}

int main()
{
	getfac();
	LL m,n;
	while(scanf("%lld %lld",&m,&n)!=EOF)
	{
		printf("%lld\n",lucas(m+n-2,m-1));
	}
	return 0;
 }