JZOJ3051. 【NOIP2012模拟10.25】單元格

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。所謂的兩種不同方案是指：隻要它們選中的單元格有一個不同，就認為是不同的方案。

Input

一行，4個整數，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。

Output

一個整數，表示不同的選擇方案數量模1000000007後的結果。

Sample Input

4000 4000 4000 14000

Sample Output

859690013

Data Constraint

對于30%的資料, 3 ≤ R, C ≤ 70。

分析

很顯然，不可能直接枚舉三個點，

那就想一些别的方法吧。

我們先分6種情況：

然後在分别考慮這3個點f相加的和。

不難發現，它們的和都是一個周長。

• 現在問題就變為求這樣矩陣的個數。

我們隻需要枚舉長和寬，再計算它們的方案數就可以了。

code(c++)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#define _ %1000000007 
using namespace std;
long long r,c,mi,mx,ans;
int main()
{
    scanf("%lld%lld%lld%lld",&r,&c,&mi,&mx);
    for(int i=;i<=r;i++)
        for(int j=;j<=c;j++)
            if(((i+j)*->=mi)&&((i+j)*-<=mx))ans=(ans+(*(((i-)*(j-))_*((r-i+)*(c-j+))_)_)_)_;
    printf("%lld",ans);
}