【普及模拟】单元格
题目描述
在一个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。所谓的两种不同方案是指：只要它们选中的单元格有一个不同，就认为是不同的方案。
输入
一行，4个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。
对于30%的数据, 3 ≤ R, C ≤ 70。
输出
一个整数，表示不同的选择方案数量模1000000007后的结果。
输入样例1
3 3 1 20000
输入样例2
3 3 4 7
输入样例3
4 6 9 12
输入样例4
7 5 13 18
输入样例5
4000 4000 4000 14000
输出样例1
6
输出样例2
0
输出样例3
264
输出样例4
1212
输出样例5
859690013
题解：
设X = calc(maxT), 表示代价在【1,maxT】的“合法”方案数，设Y=calc(mint-1)表示【1，minT-1】的“合法”方案数。那么我们的输出答案就是X-Y。如何求calc(T)呢？枚举选中的三个格子的高度差是h，那么根据代价的定义，那么这三个被选中的格子的宽度差w 一定不能超过(T-2*h)/2，当确定了高度差h后，由于三个单元格不能同行也不能同列
设a,b,c是三个被选中的单元格，那么形状有如下6大类：
情况一：
情况二：
情况三：
情况四：
情况五：
情况六：
如果能求出上面的任意一类，其它情况则同理计算，而且这6大类的方案数是相等的。
下面来分析“情况一”：
枚举的h是高度差，没必要枚举上边界和下遍界，因为只要高度差相同，那么合法方案数肯定就相同，算出高度差是h的方案数后，再乘以(r-h)即可。当h通过枚举确定后，w的最大值也确定了，最简单的方法是枚举格子a和格子c, 然后统计格子b的可能性，但是这种枚举是低效的。我们不妨设格子a目前在第1列，由于w的最大值是确定的，那么c格子的列编号最大值是等于w+1, 最小值是3。当c的列编号等于1+w时，格子b的选择有(h-1)w种，当格子c的列编号等于w时，格子b的选择有(h-1)(w-1)种，格子c的列编号等于w-1时，格子b的选择有(h-1)(w-2)种….直到格子a、b、c是连续的三列，此时格子b的选择有(h-1)*1种，于是当格子a的位置确定后，合法的方案数是：(h-1) ( w + (w-1)+(w-2)+(w-3)+…1)。记sum[w] = w + (w-1)+(w-2)+(w-3)+…1，这个部分和是可以预处理的。同理，当格子a的列编号等于2时，那么c格子所在列的最大编号是w+2，只要w+2不大于题目给出的列数，那么答案还是和之前算的相同，这样的话，可以直接用乘法算了，即sum[w]*(c-w)。当然，会有一些边界需要特殊计算，请读者自行推理一遍。
时间复杂度是：O( r )。
标程：
var
i,j,k,l,n,m,min,max,r:longint;
ans,x,y:int64;
begin
assign(input,'table.in');reset(input);
assign(output,'table.out');rewrite(output);
readln(n,m,min,max);
for i:=min to max do
begin
if i mod 2=0 then
begin
l:=i div 2;
for j:=3 to l do
begin
r:=j-2;
k:=l-j;
if(r+2<=n)and(k+2<=m)and(r+2>=3)and(k+2>=3) then
begin
x:=(n-r-1)*(m-k-1) mod 1000000007;
y:=(4*r*k+2*r*k) mod 1000000007;
ans:=(ans+x*y) mod 1000000007;
end;
end;
end;
end;
writeln(ans);
close(input);close(output);
end.