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 //挺懵逼的，虽然看出动规后是个杨辉三角，但不知道
杨辉三角的性质，第 n 行 第 m 位为 C(n-1,m-1) 这也是组合数递推的性质 C(n,m)=C(n-1,m)+C(n-1,m-1)
输出 C(n+m-2,m-1) 即可
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007 LL n,m; LL qk_mi(LL a,LL b)
{
LL res=;
while (b)
{
if (b&) res = res*a%MOD;
a=a*a%MOD;
b/=;
}
return res;
} LL J(int x)
{
LL res=;
for (int i=;i<=x;i++)
res=res*i%MOD;
return res;
} LL C(LL x, LL y)
{
return J(x)*qk_mi(J(y)*J(x-y)%MOD,MOD-)%MOD;
} int main()
{
scanf("%lld%lld",&n,&m);
LL ans = C(n+m-,m-);
printf("%lld",ans);
return ;
}
![2022-10-05：在一个 n x n 的整数矩阵 grid 中， 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时，在时间为 t 时，水池中的水位为 t 。](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
