藏妹子之处 (excel)

问题描述

今天 CZY 又找到了三个妹子, 有着收藏爱好的他想要找三个地方将妹子们藏起来, 将一片空 地抽象成一个 R 行 C 列的表格, CZY 要选出 3 个单元格. 但要满足如下的两个条件:

  1. 任意两个单元格都不在同一行.
  2. 任意两个单元格都不在同一列.

选取格子存在一个花费, 而这个花费是三个格子两两之间曼哈顿距离的和 (如 (x1, y1) 和 (x, y2) 的曼哈顿距离为|x1-x2|+|y1-y2|). 狗狗想知道的是, 花费在 minT 到 maxT 之间的方案数有多少.

答案模 1000000007. 所谓的两种不同方案是指: 只要它选中的单元格有一个不同, 就认为是 不同的方案.

输入格式

一行, 4 个整数, R、C、minT、maxT.

\(3 \leq R, C \leq 4000, 1 \leq minT \leq maxT \leq 20000\)

对于 30% 的数据,\(3 \leq R, C \leq 70\).

输出格式

一个整数, 表示不同的选择方案数量模 1000000007 后的结果.

输入输出样例

输入样例 输出样例
3 3 1 20000 6
3 3 4 7 0
4 6 9 12 264
7 5 13 18 1212
4000 4000 4000 14000 859690013

Explanation

这道题让我想了一阵才出正解:

想办法用一个矩形把三个点框住, 然后一定有至少一个、至多三个点处在矩形的顶点上. 这样一来, 我们就可以分类讨论几个点到中心点的距离了.

这样计算出来的点的组数一定是不会重复的.

然后特判部分详细看代码~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 4010;
const lli modr = 1000000007ll;

int n, m;
lli mint, maxt, dp[maxn][maxn];

// Calculate selective methods of width w and height h
// There are no relations between the order of three points and the total cost
// if their boundaries are the same in rectangles.
lli work_result(int w, int h)
{
    // Assertion required.
    if (w < h) swap(w, h);
    // According to the drawer-theorem, there must be at LEAST one endpoint
    lli res = 0;
    // Taken into the consideration of constrained line... (i.e. h = 1)
    if (h == 1)
        return 0;
    // Upper-left only, lower-left only, ... (x4)
    res += ((w - 2) * (h - 2)) * 4;
    // Inside the boundaries (x2)
    res += ((w - 2) * (h - 2)) * 2;
    // Procedure complete.
    return res % modr;
}

int main(int argc, char** argv)
{
    scanf("%d%d%lld%lld", &n, &m, &mint, &maxt);
    lli res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int est_cost = (i - 1) * 2 + (j - 1) * 2;
            if (est_cost < mint || est_cost > maxt)
                continue;
            lli cnt_appearences = (n - i + 1) * (m - j + 1);
            res = (res + work_result(i, j) * cnt_appearences) % modr;
        }
    printf("%lld\n", res);
    return 0;
}