题目题解代码

题目

在一个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。所谓的两种不同方案是指：只要它们选中的单元格有一个不同，就认为是不同的方案。

3≤R,C≤4000, 1≤minT≤maxT≤20000。

题解

反正我是没想到 题解如下： 很明显三点的费用就是三点所在的长方形的周长，就是只要模拟行和列就可以了，有两种方法控制这个长方形。 三点都在边上，而且有一点在顶点， 三点都在边上，而且有两点在顶点， 因为有四个顶点，所以这种要乘4。 因为有两个对顶点，所以这种要乘2。 Ans=(r-2)(c-2)*4. Ans=(r-2)(c-2)*2. -2是因为顶点不算 然后再计算一下这个矩阵在原矩阵中出现了多少次就可以了。（r-i+1) , (c-j+1) 归根结底就是模拟

代码

const maxn=1000000007; var i,j:longint; k,r,c,mint,maxt:int64; begin readln(r,c,mint,maxt); for i:=3 to r do for j:=3 to c do if ((i+j-2)*2>=mint)and((i+j-2)*2<=maxt) then begin k:=(k+(i-2)*(j-2)*(r-i+1)*(c-j+1))mod maxn; end; writeln((k*6)mod maxn); end.