描述 Description
在一个 R 行 C 列的表格里，我们要选出 3 个不同的单元格。但要满足如下的两个条件：
（1）选中的任意两个单元格都不在同一行。
（2）选中的任意两个单元格都不在同一列。
假设我们选中的单元格分别是：A，B，C，那么我们定义这种选择的 “费用”= f[A][B] + f[B][C] + f[C][A]。 其中 f[A][B] 是指单元格 A 到单元格 B 的距离，即两个单元格所在行编号的差的绝对值 + 两个单元格所在列编号的差的绝对值。例如：单元格 A 在第 3 行第 2 列，单元格 B 在第 5 行第 1 列，那么 f[A][B] = |3-5| + |2-1| = 2 + 1 = 3。至于 f[B][C], f[C][A]的意义也是同样的道理。
现在你的任务是：有多少种不同的选择方案，使得 “费用” 不小于给定的数 minT，而且不大于给定的数 maxT，即 “费用” 在[minT, maxT]范围内有多少种不同的选择方案。答案模 1000000007。所谓的两种不同方案是指：只要它们选中的单元格有一个不同，就认为是不同的方案。
输入格式 InputFormat
一行，4 个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。
输出格式 OutputFormat
一个整数，表示不同的选择方案数量模 1000000007 后的结果。
样例输入 SampleInput
4000 4000 4000 14000
样例输出 SampleOutput
859690013
代码 Code
所求三点间曼哈顿距离即为包含三点的最小矩形的周长，于是枚举该矩形的长和宽，每个矩形 (长 x 宽 y) 可以有 (x-2)(y-2)6 种方案，且每个矩形都可以在表格里找到(r-x+1)(c-y+1) 个位置。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
const int mod=1000000007;
int c,mint,maxt,ans;
int main()
{
scanf("%d%d%d%d",&r,&c,&mint,&maxt);
ans=0;
for (i=3;i<=r;i++) for (j=3;j<=c;j++)
if ((i+j-2)*2>=mint && (i+j-2)*2<=maxt)
{
ans+=(((long long)i-2)*(j-2)*(r-i+1)*(c-j+1)*6)%mod;
ans%=mod;
if (ans<0) ans+=mod;
}
printf("%d\n",ans);
return 0;
}