[HZWER]藏妹子之处

问题描述

今天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

思路

　　一切解释来自于http://www.cnblogs.com/zhber/p/4036003.html

1、首先暴力枚举三个点是n^6做法、TLE……

（川汉唐说：这就是我所做的）

2、发现对于三个点(x1,y1)(x2,y2)(x3,y3)，如果任意交换坐标费用不变，即如果换成(x2,y1)(x3,y2)(x1,y3)费用不变

所以题意=枚举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,令s=2(x1+y1)则满足 minT<=2(x3-x1)+2(y3-y1)<=maxT 即(minT+s)/2<=x3+y3<=(maxT+s)/2的(x3,y3)才可以。则(x3,y3)对答案的更新即是(x2,y2)的个数，即(x3-x1-1)*(y3-y1-1).这样枚举两个点n^4、TLE……

3、限定x3=k,则(minT+s)/2-k<=y3<=(maxT+s)/2-k.且y1+2<=y3<=c.

第三个点(k,???)对答案的更新是(k-x1-1)*Σ[(minT+s)/2-k-y1-1到(maxT+s)/2-k-y1-1]

令S=(minT+s)/2-y1-1,T=(maxT+s)/2-k-y1-1,则对于x3=k,方案是(k-x1-1)*Σ[S-k到T-k]=(k-x1-1)*(S-T+1)*(S+T-2k)

这样枚举x1,y1,x3，效率n^3、TLE……

4、正解是我最后才想出来的。其实这题跟CQOI2014数三角形很像。(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)次。那么直接枚举矩形的边长，然后就可以算出答案。这样n^2、AC啦……

5、千古神犇黄巨大指出，可以套上数据结构维护，这样变成nlogn了。这我没写……

源码

川汉唐翻译的PASCAL代码

const mo=1000000007;
var ans:int64=0;
    i,j:longint;
    n,m,maxt,mint,w:int64;
begin
    readln(n,m,mint,maxt);
    for i:=3 to n do
        for j:=3 to m do
            begin
                w:=2*(i+j-2);
                if (w<=maxt)and(w>=mint) then
                    inc(ans,(n-i+1)*(m-j+1)*(i-2)*(j-2) mod mo);
            end;
    writeln(ans*6 mod mo);
end.

View Code

并不受坑题影响的昊哥解出了这道题

#include <cstdio>
#include <iostream>
#define mod 1000000007

using namespace std;


int R,C,minT,maxT;

inline int floor(int a)
{
    if (a % 2 == 0) return a / 2;
    else return a / 2 + 1;
}

inline int calc(int a,int b)
{
    return ((R - a) * (C - b));
}

int main()
{
    freopen("excel.out","r",stdin);
    freopen("excel.in","w",stdout);
    
    scanf("%d%d%d%d",&R,&C,&minT,&maxT);
    minT = max(8 , minT);
    maxT = min((R - 1) * 2 + (C - 1) * 2 , maxT);
    
    long long ans = 0;
    
    int b;
    int sum;
    long long  tmp;
    for (int S = floor(minT);S <= maxT / 2;S++)
    {
        for (int a = 2;a < R;a++)
        {
            b = S - a;
            if (!(b >= 2 && b < C)) continue;
            sum = calc(a,b);
            tmp = (a - 1) * (b - 1) * 6;
            //tmp = (a - 1) * (b - 1) * 2 + (a - 1) * (b - 1) * 4;

            tmp %= mod;
            ans += tmp * sum;
            ans %= mod;
        }
    }
    printf("%d",ans);
    
    return 0;
}

View Code