單元格

題目大意：

在一個(gè)R×C的矩形中選三個(gè)點(diǎn)，使他們行列各不同，定義“費(fèi)用”為，這三個(gè)點(diǎn)之間的行列的差值的和（1,2和3,4費(fèi)用是差值是（3-1）+（4-2）=2+2=4），問差值不小于minT，不大于maxT的三個(gè)點(diǎn)中，選定的三個(gè)點(diǎn)不同的方案有多少種（結(jié)果對(duì)1000000007取模）

數(shù)據(jù)范圍限制

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

提示

解題思路：

我們先定一個(gè)長為4（i），寬為4（j）的矩形（如下圖），這三個(gè)點(diǎn)可以在它的邊界上定義，我們先固定一個(gè)點(diǎn)（黑點(diǎn)），然后另外兩個(gè)點(diǎn)可以在另外兩條邊上定義（不能在交點(diǎn)上），這種情況的種數(shù)是(i-2)×(j-2)，因?yàn)榫匦斡兴膫€(gè)點(diǎn)，所以乘上4：4×(i-2)×(j-2)

然后我們可以固定兩個(gè)對(duì)頂點(diǎn)（如圖），然后另外一個(gè)點(diǎn)可以在中間定義，種數(shù)為(i-2)×(j-2),因?yàn)閷?duì)頂點(diǎn)有兩對(duì)所以有2×(i-2)×(j-2)種可能

合并前面兩種，則為6×(i-2)×(j-2),然后這種矩形在全圖的個(gè)數(shù)可以從下圖看出（不要問我為什么用綠色，因?yàn)槲易筮叺腃NH奆佬喜歡綠色）,他的個(gè)數(shù)是四個(gè)（行有兩個(gè)三，列有兩個(gè)三，相乘為4），則為(R-i+1)×(C-j+1),總結(jié)一下就是6×(i-2)×(j-2)×(R-i+1)×(C-j+1),然后直接枚舉i和j就行了

#include<cstdio> #include<iostream> using namespace std; long long n,m,maxx,minn,ans; int main() {scanf("%lld %lld %lld %lld",&n,&m,&minn,&maxx);for (long long i=3;i<=n;++i)//枚舉ifor (long long j=3;j<=m;++j)//枚舉jif ((i+j-2)*2<=maxx&&(i+j-2)*2>=minn)//判斷是否符合題意ans=(ans+6*(i-2)*(j-2)*(n-i+1)*(m-j+1))%1000000007;//代入公式，取模printf("%lld",ans);//輸出結(jié)果return 0; }

總結(jié)

以上是生活随笔為你收集整理的【结论】单元格（jzoj 1509）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。