M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。
收起
输入
第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000)
输出
输出走法的数量。
输入样例
2 3
输出样例
3
动态规划代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 1000
#define DMAX 10000
#define MOD 1000000007
using namespace std;
typedef long long ll;
int m,n;
ll dp[MAX + ][MAX + ]; int main() {
scanf("%d%d",&m,&n);
dp[][] = ;
for(int i = ;i <= m;i ++) {
for(int j = ;j <= n;j ++) {
dp[i][j] += dp[i][j - ] + dp[i - ][j];
dp[i][j] %= MOD;
}
}
printf("%lld",dp[m][n]);
}
可以用组合数，因为在每个位置要么选择横着走，要么选择竖着走，我们发现横着跨越的边或者竖着跨越的边的数量是一定的，分别是n - 1和m - 1，所以我们只需要把横着跨越的位置选好，或者把竖着的选好，剩下的就是横着走的了。
1,1 1,2 1,3 1,4
2,1 2,2 2,3 2,4
3,1 3,2 3,3 3,4
如上，我们先把竖着跨越的选好，显然选m-1=2个，第一个选1,2->2,2吧，第二选2,4->3,4这样我们需要连接n-1=3条边，1,1->1,2,2->2,3,2,3->2,4，横的竖的只要有一个选好了，另一个就定下了，所以只需要计算其中一个选择有几种情况即可。总的需要走n+m-2步，即需要跨越这么多个格子的边界，具体把哪几步分配给横着（竖着）走，可以用组合数来完成，而这里数据大需要取模，组合数有分子分母，取模要用到逆元。
组合代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 1000
#define DMAX 10000
#define MOD 1000000007
using namespace std;
typedef long long ll;
int m,n;
int exgcd(int a,int b,int &x,int &y) {
if(b == ) {
x = ,y = ;
return a;
}
int g = exgcd(b,a % b,y,x);
y -= a / b * x;
return g;
}
int c(int x,int y) {
ll ans = ;
int a,b;
for(int i = y;i > y - x;i --) {
ans = (ans * i) % MOD;
}
for(int i = ;i <= x;i ++) {
exgcd(i,MOD,a,b);
a = (a + MOD) % MOD;
ans = (ans * a) % MOD;
}
return ans;
}
int main() {
scanf("%d%d",&m,&n);
printf("%d",c(min(m - ,n - ),n + m - ));
}
可以用卢卡斯定理专门求组合数。
lucas代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 1000000
#define DMAX 1000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
int m,n;
ll pow_mod(ll a,ll b,ll p) {///quick_pow
ll ans = ;
while(b) {
if(b % ) ans = (ans * a) % p;
a = (a * a) % p;
b >>= ;
}
return ans;
}
ll c(ll a,ll b,ll p) {///c(b,a)
ll ans = ,temp = ;
for(int i = ;i < b;i ++) {
ans = (ans * (a - i)) % p;
temp = (temp * (b - i)) % p;
}
temp = pow_mod(temp,p - ,p);///变成逆元 费马定理
ans = (ans * temp) % p;
return ans;
}
ll lucas(ll a,ll b,ll p) {//main
ll ans = ;
while(a && b) {
ans = (ans * c(a % p,b % p,p)) % p;
a /= p;
b /= p;
}
return ans;
}
int main() {
scanf("%d%d",&m,&n);
printf("%d",lucas(n + m - ,n - ,MOD));
}