题目

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

 收起

输入

第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000000)

输出

输出走法的数量 Mod 10^9 + 7。

输入样例

2 3

输出样例

3

解题思路:从左上角走到右下角需要往右走m-1步，需要向下走n-1步。所以一共m+n-2次移动,其中n-1次向下,所以答案为,直接用公式求，除法时需要用到乘法逆元，因为mod为素数，且n，m < mod，所以1~n-1都与mod互素,直接用费马小定理求逆元.

代码:

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; ll qpow(ll a,ll b,ll mod){ ll ans = 1; while(b){ if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } int main(){ ll m,n,ans = 1; cin>>m>>n; n--,m--; for(int i = 0;i < n;++i) ans = ans * (m + n - i) % mod; for(int i = 2;i <= n;++i) ans = ans * qpow(i,mod - 2,mod) % mod; cout<<(ans % mod + mod) % mod <<endl; return 0; }