【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;
 }