2018 ccpc final（补题）:G. Pastoral Life in Stardew Valley

final（补题）:G. Pastoral Life in Stardew Valley"/>

2018 ccpc final（补题）:G. Pastoral Life in Stardew Valley

题目大意：在一个n * m的土地，要在一个子矩形内放稻草人，稻草人必须被稻草包围，问有几种方法？

解法：可以将子矩形的长和宽分开考虑，因为长和宽分别选定可以唯一确定一个子矩形，注意到对于一个n * m的土地，最多有中间(n - 2) * (m - 2) 这么大的范围可以放稻草人，从这个点入手可以推出用这么大范围放稻草人的方案数：(n -1 ) * (n - 2) * (m - 1) * (m - 2) / 4，但这并不是答案，因为还可以种草使得可以放稻草人的范围缩减。难道要枚举所有可能的规模然后求和吗？（NO）

问题其实可以转化为：在n * m的草地上，选出一块子矩形，这个子矩形来放满稻草人必须被包括在n * m的矩形内。行和列分开考虑，行的方案数 * 列的方案数就是答案。行有几种可能呢？ 因为选出的子矩形必须周围有草，先从一行考虑列，一行可以选4个点，里面两个点是子矩形的宽的边界（列的边界），外面两个点是边界（这两个点以外包括这两个点都是草，放稻草的矩形外面一定要被草包围，但不必贴紧包围，可以留出空隙，因此要这样选），发现这样能确定一个子矩形的列的情况，但还有一种遗漏，就是只有一列的子矩形，这种情况只需要选三个点，所以是c[m][3] + c[m][4]， 这样就确定了列的所有方案，再乘上行的所有方案就是总答案，行的方案跟列的方案类似。

反思：一看题解感觉也不难，比赛的时候人跟懵逼了一样疯狂打表找规律，找了半个小时都没放弃，也没发现数字其实就是杨辉三角形的一条斜线，不过这都不是最重要的，最重要的是始终没有从行和列的角度去思考这道题，一直想从递推的方式，想要能缩减掉一维使得得出答案表的复杂度可以降低。还是思维上的问题。
（不过队友硬性推出了一个逆天的公式，还搞过去了，服服帖帖）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
long long c[maxn][5];
int t,n,m;
int main() {c[0][0] = 1;for(int i = 1; i <= maxn; i++) {c[i][0] = 1;for(int j = 1; j <= 4; j++)c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}scanf("%d",&t);int ca = 0;while(t--) {scanf("%d%d",&n,&m);printf("Case %d: ",++ca);printf("%lld\n",((c[n][3] + c[n][4]) % mod) * ((c[m][3] + c[m][4]) % mod) % mod);}return 0;
}