这题首先是找规律推公式，然后就是组合数学的知识了。
题目是问到第n行第m列的格式有几种方案，我们可以用手算的方法列出当n和m比较小时的所有答案
比如我列出以下88的矩阵
924 462 210 84 28 7 1 0
462 252 126 56 21 6 1 0
210 126 70 35 15 5 1 0
84 56 35 20 10 4 1 0
28 21 15 10 6 3 1 0
7 6 5 4 3 2 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 1
矩阵上的数表示从那个位置到最右下角一共有多少种方案。
求每个位置的值也简单，就是把它右下角的所有数加起来即可。
那么，把这个矩阵倒过来看，就是想要的结果矩阵了。
规律也很容易发现，首先，矩阵是对称的，所以我是只考虑m>=n的情况。
然后，可以发现每个位置的数就是一个组合数C(m + n - 4, n - 2)
最后就是求组合数取模了，C(m + n - 4, n - 2) %
然而，多年没做题的我，并不会组合数取模。找了以前的模板，是竹教主写的，看了好半天才明白，等我打完的时候，比赛刚结束。
比赛结束后交了一次，果然a了T_T
以下是代码
/
baidu/win.cpp
Created on: 2016-5-22
Author : ben
/
#include
#include
#include
#include
#include
#include
#include
#include
#include [span style="color: rgba(0, 0, 255, 1)">set
#include
#include
#include [span style="color: rgba(0, 0, 255, 1)">string
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL Ext_gcd(LL a, LL b, LL x, LL y) {
if (b == 0) {
x = 1, y = 0;
return a;
}//代码效果参考：http://www.ezhiqi.com/zx/art_1460.html
LL ret = Ext_gcd(b, a % b, y, x);
y -= a / b x;
return ret;
}
LL Inv(LL a, int m) { ///求除数a对m的逆元；
LL d, x, y, t = (LL) m;
d = Ext_gcd(a, t, x, y);
if (d == 1)
return (x % t + t) % t;
return -1;
}
void work(int n, int m) {
int i;
const int mod = 1000000007;
LL sum = 1;
for (i = n - m + 1; i <= n; i++) {
sum = (LL) i;
sum %= mod;
}
LL tmp = 1;
for (i = 2; i <= m; i++)
tmp = i, tmp %= mod;
sum = Inv(tmp, mod);
sum %= mod;
printf("%I64d\n", sum);
}
int main() {
int n, m;
while (scanf("%d%d", n, m) == 2) {
if (m [span style="color: rgba(0, 0, 0, 1)"> n) {
int tmp = m;
m = n;
n = tmp;
}//代码效果参考：http://www.ezhiqi.com/zx/art_2396.html
work(m + n - 4, n - 2);
}
return 0;
}
