【NOIP模擬賽】藏妹子之處

問題描述：

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

（1）任意兩個單元格都不在同一行。

（2）任意兩個單元格都不在同一列。

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

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

輸入格式：

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

對於30%的數據, 3 ≤ R, C ≤ 70。

輸出格式:

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

輸入輸出樣例：

3 3 1 20000        3 3 4 7        4 6 9 12        7 5 13 18        4000 4000 4000 14000

6                         0                 264               1212               859690013

題解

很容易發現發現對於三個點(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<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define ll long long
 8 using namespace std;
 9 int n,m,minn,maxx,ans;
10 int ta[10005],tb[10005];
11 int main()
12 {
13     int i,j;
14     scanf("%d%d%d%d",&n,&m,&minn,&maxx);
15     for(i=1;i<=n;i++) ta[i]=(n-i)*(i-1);
16     for(i=1;i<=m;i++) tb[i]=(m-i)*(i-1);
17     for(i=1;i<=n;i++)
18      for(j=1;j<=m;j++)
19         if(2*(i+j)>=minn&&2*(i+j)<=maxx) ans=(ans+(ll)ta[i]*tb[j]*6%1000000007)%1000000007;
20     printf("%d",ans);
21     return 0;
22 }