[数据结构与算法]2021-10-22

题目
题目看了很久才看懂，然后自己又研究了很久，虽然找出一点规律，但是暴力写，必然无法过。悲伤，看别人的题解，才觉得精妙无比，需要从行和列分别考虑。
题意：就是一个稻草人周围必须都稻草。稻草人占据一个矩形，问符合这样条件的矩形有多少个？
计算过程如下：令$x=n?2$，$y=m?2$，对于一个$n?m$的矩形，最先寻找$x?y$中存在多少子个矩阵；然后再分别寻找$(n?1)?m$的矩形$(x?1)?y$的矩形中存在多少子个矩阵或是$n?(m?1)$的矩形中$x?(y?1)$的矩形中存在多少个矩形；接下来以此类推，直到 $n=3$ 且 $m=3$。
对于$x$行，一列的矩形个数为 $f(x)=\frac{x(x+1)}{2}$；
对于$y$列，一行的矩形个数为 $f(y)=\frac{y(y+1)}{2}$；
对于每一个$n?m$的矩形的子矩阵数量总和，为
$[f(x)+2f(x?1)+3f(x?2)+...+xf(1)]?[f(y)+2f(y?1)+3f(y?2)+...+yf(1)]$
在此可以利用前缀和的想法来实现（本菜鸡学到了，真的是精妙）
利用数组$sum1[i]=sum1[i]+f[i]$，和数组$sum2[i]=sum2[i]+sum1[i]$进行实现，$sum2[x]?sum2[y]$即为一个$n?m$矩形的子矩阵总和。
以下代码就是分别从行和列中进行计算：

#include <bits/stdc++.h>
using namespace std;
#define T int T; scanf("%d", &T); while(T--)
typedef long long ll;
const int N=1e5+1;
const int mod=1e9+7;
ll sum1[N], sum2[N], d[N];

void init(){
	for(ll i=1; i<N; i++){
		d[i]=i*(i+1)/2;
		d[i]%=mod;
	}

	for(ll i=1; i<N; i++){
		sum1[i]=(sum1[i-1]+d[i])%mod;
	}

	for(ll i=1; i<N; i++){
		sum2[i]=(sum2[i-1]+sum1[i])%mod;
	}
}

int main()
{
	init();
	int t=1;
    T{
    	ll n, m;
    	scanf("%lld %lld", &n, &m);
    	if(n<3 || m<3){
    		printf("Case %d: 0\n", t++);
    	} else {
    		printf("Case %d: %lld\n", t++, ((sum2[n-2]%mod)*(sum2[m-2])%mod)%mod);
    	}
    }
	return 0;
}