按 v 把限制分层,每层用并集面积差定出可填 v 的格子,再对同值矩形做子集容斥,各层相乘。
OJ: roj
题目 ID: 1783
难度:提高
标签:容斥状压组合数学python
创建: 2026-10-08 02:22
更新: 2026-10-08 02:22
形式化题目
有一个
两种方案不同当且仅当存在某个格子上的数不同。输入多组数据:第一行是组数 x1 y1 x2 y2 v(双闭区间)。
数据规模:
正解
思路
朴素做法是枚举所有
第一步:把「恰好等于
- 该子矩阵的每个格子都
(上界约束); - 该子矩阵里至少有一个格子取到了
(下界约束)。
于是每个格子先有一个上界:若它同时落在若干限制矩形内,则
第二步:按上界的取值分层,层与层互不相干。
对目标值为
而不同的
第三步:每层做子集容斥。
固定一个
- 被
中矩形覆盖到的 格子只能填 ,面积记为 ; - 其余
格子不受这条强制影响,仍可填 。
所以该层的答案是
其中
最后一步:面积怎么算。 两个量只需要面积,不需要逐格判断:
: 就是「被 与所有更小的 的矩形覆盖的格子」减去「只被更小的 覆盖的格子」,即 ,其中 是 更小的 那些矩形的集合; :同理是 。
把所有矩形的集合用
把一切拼起来:自由格子
以样例第一组
层: (4 格),只能填 , ; 层: 是 里上界仍为 的 3 格。要求 中至少一格取 , 容斥为 ; - 自由格子:
格,各 种,共 种。
总方案
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:预处理
用 ,并集容斥 ;每层枚举 个子集、每个子集两次查表加三次快速幂,总共 次, 即 。 时基本运算是 级别, 也远低于 2000 ms 的限时。 - 空间:两个长度
的 long long表加上个矩形, , 约几十 KB。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两个版本:同样用掩码 求交集 / 并集面积,同样按分层做子集容斥,复杂度同阶。Python 的 pow(base, exp, MOD)是内建快速幂,因此不存在需要手写的幂运算;常数虽大 10 倍以上,但、 的运算量极小,Python 侧也没有 TLE 风险。
总结
- 抓住最小的那个量:
都可以到 ,唯一小的是 。 一切指数级手段(枚举子集)都必须挂在 上,而不是挂在格子数上。 - 「最大值恰好为
」= 上界约束 + 至少一次命中:拆开后,上界约束决定每个格子 能填什么( ),命中约束只落在 的格子上——这一步把不同的 彻底解耦。 - 层与层解耦是本题的关键不变量:每个格子只属于一层(它唯一的上界值),
所以各层的方案数可以独立相乘;如果允许格子跨层共享,容斥就必须同时处理多个
, 问题会难得多。 - 只需要面积,不需要具体格子:
与 都写成两个并集面积之差, 于是「几何」部分被压缩成 个掩码上的数字,容斥只需查表。 的边界:此时 , 在 时为 (那些格子无处可填),在 时为 (没有格子受影响)。 快速幂把 约定为 ,正好符合容斥的语义,不必特判。 - 无解自然浮现:诸如「大矩形
里套一个 的小矩形」这类矛盾, 表现为某层的容斥结果恰为 ,总答案随之变 ,无需单独写判无解的分支。 - 本题素材说明:题目目录里带有数据生成脚本(
data.py),说明本地测试点是 重新构造的,而非官方原始数据;题面与 FJOI2017 / 洛谷 P3813《矩阵填数》一致 (样例答案、 相同),思路按题面独立推导, std.cpp仅用作交叉核对。