51nod 1119-机器人走方格V2(组合数学+乘法逆元+快速幂)

51nod 1119

【分析】如果n,m范围小点，就是最基础的DP，但是这题n,m<=10^6，不能DP；其实就是个简单的组合数学(然而已经忘记了)：

从(1,1)走到(n,m)一共需要往下走n-1步，往右走m-1步，那么一共可能的路径数量就是从(n-1+m-1)中选择出(n-1)条往下走，那么组合数就是C(n-1+m-1,n-1)；有除法，加个快速幂逆元就好了。

【AC CODE】46ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 2000000+10;
const LL MOD = (LL)1e9+7;
LL f[MAXN];

LL pow_mod(LL x, int n)
{
	LL ans = 1;
	while(n)
	{
		if(n&1) ans = ans*x%MOD;
		x = x*x%MOD;
		n >>= 1;
	}
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,m;
	scanf("%d%d", &n, &m);
	f[1] = 1;
	repe(i,2,n+m-2) f[i] = f[i-1]*i%MOD;
	LL a = f[n+m-2], b = f[m-1]*f[n-1]%MOD;
	printf("%lld\n", a*pow_mod(b,MOD-2)%MOD);
	return 0;
}