暑假訓練-藏妹子之處(遞推)

【題目描述】：

今天CZY又找到了三個妹子，有着收藏愛好的他想要找三個地方将妹子們藏起來，将一片空地抽象成一個R行C列的表格，CZY要選出3個單元格。但要滿足如下的兩個條件：

1. 任意兩個單元格都不在同一行。
2. 任意兩個單元格都不在同一列。

選取格子存在一個花費，而這個花費是三個格子兩兩之間曼哈頓距離的和（如(x1,y1)和(x,y2)的曼哈頓距離為|x1-x2|+|y1-y2|）。狗狗想知道的是，花費在minT到maxT之間的方案數有多少。

答案模1000000007。所謂的兩種不同方案是指：隻要它選中的單元格有一個不同，就認為是不同的方案。

【輸入描述】：

一行，4個整數，R、C、minT、maxT。

【輸出描述】：

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

【樣例輸入1】：

3 3 1 20000      

【樣例輸出1】：

6      

【樣例輸入2】：

3 3 4 7      

【樣例輸出2】：

【樣例輸入3】：

4 6 9 12      

【樣例輸出3】：

264      

【樣例輸入4】：

7 5 13 18      

【樣例輸出4】：

1212      

【樣例輸入5】：

4000 4000 4000 14000      

【樣例輸出5】：

859690013      

【時間限制、資料範圍及描述】：

時間：1s 空間：128M

對于 30%的資料： 3<=R,C<=70。

對于100%的資料： 3<=R,C<=4000, 1<=minT<=maxT<=20000。

很容易發現發現對于三個點(x1,y1)(x2,y2)(x3,y3)，如果任意交換坐标費用不變，是以題意變為枚舉3個橫坐标和3個縱坐标，算合理的方案數

對于x1,x2,x3 , y1,y2,y3，若有x1<x2<x3 , y1<y2<y3，則方案的費用是2(x3-x1)+2(y3-y1)。

是以，不妨令x1<x2<x3 , y1<y2<y3，則由排列組合易得，最後方案數乘6即為答案。

而(x1,y1)和(x3,y3)構成一個矩形，對于一個确定的矩形邊框，它的費用是一定的，即2(x3-x1)+2(y3-y1)，也就是矩形的邊長。它對答案的貢獻也是一定的，即(x3-x1-1)*(y3-y1-1)。這個矩形在r*c的大矩形中出現的次數也是給定的，設矩形長為x,寬為y，則出現了(r-x+1)*(c-y+1)次。那麼直接枚舉矩形的邊長，然後就可以算出答案。

時間複雜度為O(n^2)

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int mod=1000000007;
 5 LL ans;
 6 LL r,c,mn,mx;
 7 int main(){
 8     freopen ("excel.in","r",stdin);
 9     freopen ("excel.out","w",stdout);
10     int i,j,d;
11     scanf("%lld%lld%lld%lld",&r,&c,&mn,&mx);
12     for (i=3;i<=r;i++){
13         for (j=3;j<=c;j++){
14             d=2*((i-1)+(j-1));
15             if (d>=mn && d<=mx)
16                 ans=(ans+(i-2)*(j-2)%mod*(r-i+1)%mod*(c-j+1)%mod*6%mod)%mod;
17         }
18     }
19     printf("%lld",ans);
20     return 0;
21 }
22