机器人走方格 V2 51Nod

题意：

(M imes N) 的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出 (Mod 10^9+7)的结果。

分析：

这是一个可重集合的排列问题。有两种不同类型的对象，个数分别为：
(R)：(n-1)
(D)：(m-1)
由公式：

[ans=frac{n!}{n_1!*n_2!*...*n_k!} ]

所以最终结果为：

[ans=frac{(n+m-2)!}{(n-1)!*(m-1)!}=frac{(n+m-2)*..*m}{(n-1)*...*1} ]

利用费马小定理求逆元，结果乘法的性质，即可求出 ((n-1)!) 的逆元。

此外，如果不用公式。方案的种类数取决于 (D) 的出现位置，有 (C(n+m-2,m-1)) 种可能，和上面的结果一样。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll power(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int main()
{
    ll m,n,res=1,d=1;
    scanf("%lld%lld",&m,&n);
    for(ll i=m;i<=n+m-2;i++)
        res=res*i%mod;
    for(ll i=1;i<n;i++)
    {
        ll t=power(i,mod-2);
        d=t*d%mod;
    }
    printf("%lld
",res*d%mod);
    return 0;
}