矩阵填数

GitHub跳转原题关系图返回列表

按 v 把限制分层,每层用并集面积差定出可填 v 的格子,再对同值矩形做子集容斥,各层相乘。

OJ: roj

题目 ID: 1783

难度:提高

标签:容斥状压组合数学python

创建: 2026-10-08 02:22

更新: 2026-10-08 02:22

形式化题目

有一个 hh 行 ww 列的矩阵,每个格子要填入 1∼m1 \sim m 中的某个整数。另外给出 nn 个限制, 第 ii 个限制形如「子矩阵 Si=[x1,i,x2,i]×[y1,i,y2,i]S_i = [x_{1,i}, x_{2,i}] \times [y_{1,i}, y_{2,i}] 内的最大值 恰好等于 viv_i」。求满足全部 nn 个限制的填数方案数,答案对 109+710^9 + 7 取模。

两种方案不同当且仅当存在某个格子上的数不同。输入多组数据:第一行是组数 TT, 每组第一行给出 h,w,m,nh, w, m, n,随后 nn 行每行给出 x1 y1 x2 y2 v(双闭区间)。

数据规模:T≤5T \le 5,1≤h,w,m≤1041 \le h, w, m \le 10^4,1≤v≤m1 \le v \le m,1≤n≤101 \le n \le 10。 注意格子总数 h⋅wh \cdot w 可达 10810^8,逐格枚举绝无可能;而限制条数 n≤10n \le 10, 这正是本题的突破口。

正解

思路

朴素做法是枚举所有 mh⋅wm^{h \cdot w} 种填法再逐条验证。格子总数最多 10810^8, 连状态都存不下,直接出局。

第一步:把「恰好等于 viv_i」拆成两半。 aa 是某个子矩阵的最大值且恰好为 vv,等价于

  1. 该子矩阵的每个格子都 ≤v\le v(上界约束);
  2. 该子矩阵里至少有一个格子取到了 vv(下界约束)。

于是每个格子先有一个上界:若它同时落在若干限制矩形内,则

L(c)=min⁡{ vi:c∈Si },没有任何限制覆盖时 L(c)=m.L(c) = \min \{\,v_i : c \in S_i\,\}, \qquad \text{没有任何限制覆盖时 } L(c) = m .

第二步:按上界的取值分层,层与层互不相干。 对目标值为 vv 的矩形 SiS_i,能帮它达成「取到 vv」的格子必须同时满足:c∈Sic \in S_i 且 L(c)≥vL(c) \ge v;而 c∈Sic \in S_i 又强制 L(c)≤vi=vL(c) \le v_i = v。两边夹起来,只有 L(c)=vL(c) = v 的格子 才有资格。也就是说

能取到 v 的格子  =  { c:L(c)=v }  =  Av,\text{能取到 } v \text{ 的格子} \;=\; \{\,c : L(c) = v\,\} \;=\; A_v ,

而不同的 vv 对应的 AvA_v 显然两两不交(一个格子只有一个上界值)。 更妙的是 L(c)=vL(c) = v 意味着 cc 一定落在某个目标值为 vv 的矩形里,所以这些格子 只需要被同一层的矩形「瓜分」,不同 vv 的层完全解耦:先算出每层 AvA_v 上的填法数, 再乘以所有上界为 mm 的自由格子(m#自由格子m^{\#\text{自由格子}}),乘法原理收尾。

第三步:每层做子集容斥。 固定一个 vv,设目标值等于 vv 的矩形下标集合是 MM。要求是:对每个 i∈Mi \in M, SiS_i 里都至少有一个 AvA_v 中的格子取值为 vv。反面是「存在某个矩形内部一个 vv 都没有」, 用容斥:枚举 MM 中「被强制取不到 vv」的矩形子集 TT,带符号 (−1)∣T∣(-1)^{|T|},此时

  • 被 TT 中矩形覆盖到的 AvA_v 格子只能填 1∼v−11 \sim v-1,面积记为 cov(T)\mathrm{cov}(T);
  • 其余 AvA_v 格子不受这条强制影响,仍可填 1∼v1 \sim v。

所以该层的答案是

ways(v)  =  ∑T⊆M(−1)∣T∣ (v−1)cov(T)⋅v ∣Av∣−cov(T).\mathrm{ways}(v) \;=\; \sum_{T \subseteq M} (-1)^{|T|} \,(v-1)^{\mathrm{cov}(T)} \cdot v^{\,|A_v| - \mathrm{cov}(T)} .

其中 T=∅T = \varnothing 项就是 v∣Av∣v^{|A_v|},即「先不管下界约束」的基础计数。

最后一步:面积怎么算。 两个量只需要面积,不需要逐格判断:

  • ∣Av∣|A_v|:AvA_v 就是「被 MM 与所有更小的 vv 的矩形覆盖的格子」减去「只被更小的 vv 覆盖的格子」,即 ∣⋃(M∪L)∣−∣⋃L∣\big|\bigcup (M \cup L)\big| - \big|\bigcup L\big|,其中 LL 是 vv 更小的 那些矩形的集合;
  • cov(T)\mathrm{cov}(T):同理是 ∣⋃(T∪L)∣−∣⋃L∣\big|\bigcup (T \cup L)\big| - \big|\bigcup L\big|。

把所有矩形的集合用 n≤10n \le 10 位的掩码表示,预处理出每个掩码的交集面积, 再用容斥 $\big|\bigcup_{i \in \text{mask}} S_i\big| = \sum_{\varnothing \ne sub \subseteq \text{mask}} (-1)^{|sub|+1}\big|\bigcap_{i \in sub} S_i\big|$ 得到并集面积表。之后 ∣Av∣|A_v| 与 cov(T)\mathrm{cov}(T) 都是两次查表相减,O(1)O(1)。

把一切拼起来:自由格子 mh⋅w−∣⋃Si∣m^{h \cdot w - |\bigcup S_i|} 乘以每层的 ways(v)\mathrm{ways}(v)。 若某一层算出 00(例如大矩形 v=1v=1 套小矩形 v=2v=2,把小矩形的上界压到 11, 没有格子能取到 22,容斥结果自然为 00),总答案就是 00,不需要额外判无解。

以样例第一组 h=w=3h = w = 3、m=2m = 2,限制为 S1=[1,2]2  (v=2)S_1 = [1,2]^2\;(v = 2)、 S2=[2,3]2  (v=1)S_2 = [2,3]^2\;(v = 1) 为例。两个矩形只在 (2,2)(2,2) 重叠,重叠格的上界被压到 min⁡(2,1)=1\min(2,1) = 1,于是各格的上界分别是:S1S_1 内其余 3 格为 22,S2S_2 的 4 格为 11, 剩下 2 个角落格 (1,3),(3,1)(1,3), (3,1) 不被任何限制覆盖、上界为 m=2m = 2。按层算:

  • v=1v = 1 层:A1=S2A_1 = S_2(4 格),只能填 11,ways(1)=14=1\mathrm{ways}(1) = 1^4 = 1;
  • v=2v = 2 层:A2A_2 是 S1S_1 里上界仍为 22 的 3 格。要求 S1S_1 中至少一格取 22, 容斥为 23−(2−1)3⋅23−3=8−1=72^3 - (2-1)^3 \cdot 2^{3-3} = 8 - 1 = 7;
  • 自由格子:22 格,各 22 种,共 22=42^2 = 4 种。

总方案 1⋅7⋅4=281 \cdot 7 \cdot 4 = \mathbf{28},与样例一致。注意 (2,2)(2,2) 只属于 v=1v = 1 层 (它是 S2S_2 里取到 11 的见证),而 S2S_2 的「取到 11」这一要求由整层一起满足, 不存在重复计数——这正是「每格只有一个上界值、各层正交」的直接体现。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 02:22
# update_at: 2026-10-08 02:22

import sys
from collections.abc import Iterator

MOD = 1000000007

# 限制子矩形:(x1, x2, y1, y2, v),横纵坐标都用左闭右开区间,v 是"内部最大值"
type Rect = tuple[int, int, int, int, int]


def submasks(mask: int) -> Iterator[int]:
    """降序产出 mask 的全部非空子掩码(标准 (sub-1)&mask 迭代)。"""
    sub = mask
    while sub:
        yield sub
        sub = (sub - 1) & mask


def build_areas(rects: list[Rect], h: int, w: int) -> list[int]:
    """返回"并集面积表"uni,uni[mask] = mask 里所有子矩形覆盖的格子总数。

    中间量是交集面积表 inter:先对每个掩码直接交边界,再用容斥 Σ(-1)^(|sub|+1)·inter[sub]
    合成并集。格子数最大 h·w = 1e8,用 Python 整数不会溢出。
    """
    n = len(rects)
    inter = [0] * (1 << n)
    for mask in range(1, 1 << n):
        x1, x2, y1, y2 = 1, h + 1, 1, w + 1
        for i, (a, b, c, d, _v) in enumerate(rects):
            if mask >> i & 1:
                x1, x2 = max(x1, a), min(x2, b)
                y1, y2 = max(y1, c), min(y2, d)
        inter[mask] = max(0, x2 - x1) * max(0, y2 - y1)

    uni = [0] * (1 << n)
    for mask in range(1, 1 << n):
        uni[mask] = sum(
            inter[sub] if sub.bit_count() % 2 else -inter[sub] for sub in submasks(mask)
        )
    return uni


def layer_ways(v: int, same: int, lower: int, uni: list[int]) -> int:
    """值为 v 的整层方案数:这层每个限制矩形的内部都必须出现 v。

    只有"上界恰好为 v"的格子能取到 v,它们构成集合 A_v(面积 size,且各层互不相交)。
    对"被强制取不到 v 的矩形集合" T 做容斥:T 覆盖到的格子只能填 1..v-1(面积 forced),
    其余格子仍可填 1..v。v-1 = 0 时 0 的正数次幂为 0,恰好表示"这些格子无处可填"。
    """
    size = uni[same | lower] - uni[lower]
    total = pow(v, size, MOD)
    for t in submasks(same):
        forced = uni[t | lower] - uni[lower]
        one = pow(v - 1, forced, MOD) * pow(v, size - forced, MOD) % MOD
        total += -one if t.bit_count() & 1 else one
    return total % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        h, w, m, n = next(data), next(data), next(data), next(data)

        rects: list[Rect] = []
        for _ in range(n):
            x1, y1, x2, y2, v = next(data), next(data), next(data), next(data), next(data)
            rects.append((x1, x2 + 1, y1, y2 + 1, v))  # 双闭区间转左闭右开
        rects.sort(key=lambda r: r[4])                  # 按 v 升序,v 小的层先算

        uni = build_areas(rects, h, w)
        ans = pow(m, h * w - uni[-1], MOD)  # 未被任何限制覆盖的格子:随便填 1..m

        lower = 0  # 已处理完的、v 更小的那些限制的掩码
        i = 0
        while i < n:
            v = rects[i][4]
            j, same = i, 0
            while j < n and rects[j][4] == v:  # 同 v 的限制合成一层,一起容斥
                same |= 1 << j
                j += 1
            ans = ans * layer_ways(v, same, lower, uni) % MOD
            if ans == 0:  # 某一层已经不可能满足,再乘下去也还是 0
                break
            lower |= same
            i = j

        out.append(str(ans))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 02:22
 * update_at: 2026-10-08 02:22
 */
// main.cpp:矩阵填数。每个格子填 1..m,n 个子矩形要求「内部最大值恰好等于 v」。
// 做法:先用容斥把每个子集的交集 / 并集面积算出来,再按 v 从小到大分层,
// 对每一层做「每个矩形都至少有一个格子取到 v」的子集容斥,各层答案相乘。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL; // 题面要求的取模数
const int MAXN = 10;         // n ≤ 10,掩码规模固定
const int MAXMASK = 1 << MAXN;

struct Rect {
    ll x1, y1, x2, y2, v; // 左上角、右下角、以及"最大值恰好为 v"
};

Rect rects[MAXN];       // 所有限制子矩形,按 v 升序排序后使用
ll inter_area[MAXMASK]; // inter_area[mask]:mask 里所有子矩形的交集面积
ll union_area[MAXMASK]; // union_area[mask]:mask 里所有子矩形的并集面积
int popcnt_arr[MAXMASK]; // 掩码的 1 的个数

ll h, w;  // 矩阵大小
int m, n; // 值的上界、限制条数

// 快速幂:0^0 约定为 1(容斥里 (v-1)^0 需要它),指数最大 h*w ≤ 1e8
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    if (base < 0) base += MOD;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

// 按 v 升序排,让"更小的层"一定排在前面
bool cmp_by_v(const Rect &a, const Rect &b) {
    return a.v < b.v;
}

// 枚举 mask 里所有子矩形的交集面积(空交集算 0)
ll intersect_area(int mask) {
    ll x1 = 1, y1 = 1, x2 = h, y2 = w;
    for (int i = 0; i < n; i++) {
        if (!((mask >> i) & 1)) continue;
        x1 = max(x1, rects[i].x1);
        y1 = max(y1, rects[i].y1);
        x2 = min(x2, rects[i].x2);
        y2 = min(y2, rects[i].y2);
        if (x1 > x2 || y1 > y2) return 0;
    }
    return (x2 - x1 + 1) * (y2 - y1 + 1);
}

void solve() {
    cin >> h >> w >> m >> n;
    for (int i = 0; i < n; i++)
        cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2 >> rects[i].v;
    sort(rects, rects + n, cmp_by_v);

    int full = (1 << n) - 1;

    // 交集面积:直接对每个子集取边界交
    for (int mask = 1; mask <= full; mask++) inter_area[mask] = intersect_area(mask);

    // 并集面积:容斥 Σ(-1)^(|sub|+1) |∩_{j∈sub} S_j|
    union_area[0] = 0;
    for (int mask = 1; mask <= full; mask++) {
        ll sum = 0;
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            if (popcnt_arr[sub] & 1) sum += inter_area[sub];
            else                     sum -= inter_area[sub];
        }
        union_area[mask] = sum;
    }

    // 未被任何限制覆盖的格子:上界为 m,可任取 1..m
    ll ans = power(m, h * w - union_area[full]);

    int lower = 0; // 已经处理过的、v 更小的那些限制的掩码
    for (int i = 0; i < n; ) {
        int j = i, same = 0; // same:本层(v 相同)的限制掩码
        while (j < n && rects[j].v == rects[i].v) {
            same |= 1 << j;
            j++;
        }
        ll v = rects[i].v;

        // 本层的格子 A_v =「被本层矩形覆盖」减去「被更小 v 覆盖」,
        // 这些格子上界恰好是 v,是唯一可能取到 v 的格子。
        ll layer = union_area[same | lower] - union_area[lower];
        ll layer_ways = power(v, layer); // 容斥里 T = 空集的那一项

        // 子集容斥:T 里的矩形被强制"没有格子取到 v",即 T 覆盖到的格子只能填 1..v-1
        for (int t = same; t > 0; t = (t - 1) & same) {
            ll forced = union_area[t | lower] - union_area[lower];
            ll one = power(v - 1, forced) * power(v, layer - forced) % MOD;
            if (popcnt_arr[t] & 1) layer_ways = (layer_ways - one + MOD) % MOD;
            else                   layer_ways = (layer_ways + one) % MOD;
        }

        ans = ans * layer_ways % MOD;
        if (ans == 0) break; // 这一层已经无法满足,后面再乘也还是 0
        lower |= same;
        i = j;
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i < MAXMASK; i++) popcnt_arr[i] = popcnt_arr[i >> 1] + (i & 1);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}

复杂度

  • 时间:预处理 ∣⋂∣\big|\bigcap\big| 用 O(2n⋅n)O(2^n \cdot n),并集容斥 O(3n)O(3^n);每层枚举 2∣M∣2^{|M|} 个子集、每个子集两次查表加三次快速幂,总共 ∑v2∣Mv∣≤2n\sum_v 2^{|M_v|} \le 2^n 次, 即 O(3n+2nlog⁡(hw))O(3^n + 2^n \log(hw))。n≤10n \le 10 时基本运算是 105∼10610^5 \sim 10^6 级别, T≤5T \le 5 也远低于 2000 ms 的限时。
  • 空间:两个长度 2102^{10} 的 long long 表加上 nn 个矩形,O(2n+n)O(2^n + n), 约几十 KB。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两个版本:同样用掩码 求交集 / 并集面积,同样按 vv 分层做子集容斥,复杂度同阶。Python 的 pow(base, exp, MOD) 是内建快速幂,因此不存在需要手写的幂运算;常数虽大 10 倍以上,但 n≤10n \le 10、T≤5T \le 5 的运算量极小,Python 侧也没有 TLE 风险。

总结

  • 抓住最小的那个量:h,w,mh, w, m 都可以到 10410^4,唯一小的是 n≤10n \le 10。 一切指数级手段(枚举子集)都必须挂在 nn 上,而不是挂在格子数上。
  • 「最大值恰好为 vv」= 上界约束 + 至少一次命中:拆开后,上界约束决定每个格子 能填什么(L(c)L(c)),命中约束只落在 L(c)=vL(c) = v 的格子上——这一步把不同的 vv 彻底解耦。
  • 层与层解耦是本题的关键不变量:每个格子只属于一层(它唯一的上界值), 所以各层的方案数可以独立相乘;如果允许格子跨层共享,容斥就必须同时处理多个 vv, 问题会难得多。
  • 只需要面积,不需要具体格子:∣Av∣|A_v| 与 cov(T)\mathrm{cov}(T) 都写成两个并集面积之差, 于是「几何」部分被压缩成 2n2^n 个掩码上的数字,容斥只需查表。
  • v=1v=1 的边界:此时 v−1=0v - 1 = 0,(v−1)cov(T)(v-1)^{\mathrm{cov}(T)} 在 cov(T)>0\mathrm{cov}(T) > 0 时为 00(那些格子无处可填),在 cov(T)=0\mathrm{cov}(T) = 0 时为 00=10^0 = 1(没有格子受影响)。 快速幂把 000^0 约定为 11,正好符合容斥的语义,不必特判。
  • 无解自然浮现:诸如「大矩形 v=1v=1 里套一个 v=2v=2 的小矩形」这类矛盾, 表现为某层的容斥结果恰为 00,总答案随之变 00,无需单独写判无解的分支。
  • 本题素材说明:题目目录里带有数据生成脚本(data.py),说明本地测试点是 重新构造的,而非官方原始数据;题面与 FJOI2017 / 洛谷 P3813《矩阵填数》一致 (样例答案 2828、7647576475 相同),思路按题面独立推导,std.cpp 仅用作交叉核对。