【JZOJ3051】單元格

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

Solution

不要想複雜了！

觀察一下發現如果一個矩陣能選出三個單元格，那麼這個矩陣選出三個單元格的每種方案的“費用”都是相同的。

于是我們枚舉子矩陣的大小，然後我們要計算出每種矩陣能選出的方案數。

設子矩陣為 r 行c列，大概有以下幾種情況（紅色部分表示要放的位置，紅色矩形表示都可以放，紅圈表示隻能放一個），每種方案數都是 (r−2)(c−2) ：

像這樣有兩點固定在矩陣四角的有兩種情況。

像這樣一個點固定在四角，其它兩個點在邊上活動的有四種情況。

總共就是六種情況。

然後再計算一下這個矩陣在原矩陣中出現了多少次就可以了。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define N 4001
#define mo 1000000007
#define ll long long
using namespace std;
int main()
{
    int n,m,minl,maxl;
    cin>>n>>m>>minl>>maxl;
    ll ans=;
    fo(i,,n)
    fo(j,,m)
    if((i+j-)*>=minl && (i+j-)*<=maxl)
    ans=(ans+(i-)*l*(j-)*l*(n-i+)*l*(m-j+))%mo;
    cout<<ans*%mo;
}