原题呈现

P3813 矩阵填数#

题目描述#

给定一个 $h \times w$ 的矩阵，矩阵的行编号从上到下依次为 $1 \sim h$ ，列编号从左到右依次 $1 \sim w$ ．

在这个矩阵中你需要在每个格子中填入 $1 \sim m$ 中的某个数．

给这个矩阵填数的时候有一些限制，给定 $n$ 个该矩阵的子矩阵，以及该子矩阵的最大值 $v$ ，要求你所填的方案满足该子矩阵的最大值为 $v$ ．

现在，你的任务是求出有多少种填数的方案满足 $n$ 个限制．

两种方案是不一样的当且仅当两个方案至少存在一个格子上有不同的数．由于答案可能很大，你只需要输出答案对 $10 ^ 9 + 7$ 取模后的结果．

输入格式#

输入数据的第一行为一个数 $T$ ，表示数据组数．

对于每组数据，第一行为四个数 $h,w,m,n$ ．

接下来 $n$ 行，每一行描述一个子矩阵的最大值 v．每行为五个整数 $x1,y1,x2,y2,v$ ，表示一个左上角为 $(x1,y1)$ ,右下角为 $(x2,y2)$ 的子矩阵的最大值为 $v$ ． $1 \le x1 \le x2 \le h$ , $1 \le y1 \le y2 \le w$

输出格式#

对于每组数据输出一行，表示填数方案 mod $1,000,000,007$ 后的值．

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

对于 $20\%$ 的数据， $n \le 2$ ．

另有 $20\%$ 的数据， $1 \le h, w \le 50$ ．

对于 $100\%$ 的数据， $T \le 5$ ， $1 \le h, w, m \le 10 ^ 4$ ， $1 \le n \le 10$ ， $1 \le v \le m$ ．

先考虑 $n=0$ 的情况．

此时，所有填数都没有限制，则显然，答案为 $(hw)^m$ ．

$n=1$ 时呢？

此时只有一个限制矩形，设这个矩形面积为 $S$ ，则可行的方案数为：矩形外随便填，存在 $(hw-S)^m$ 种填法．矩形内则是限制每一个元素都要小于等于 $v_1$ ，且必须要有 $v_i$ 存在．那么矩形内合法的方案数为每一个元素都小于等于 $v_1$ 的方案数，减去没有元素是 $v_1$ 的方案数（即所有元素都小于等于 $v_1-1$ 的方案数）．矩形外和矩形内互不干涉，故将两者方案数答案相乘即为答案．

$n=2$ 时呢？

矩形外仍是随便填，矩形内呢？显然，只被矩形 1 包括的点需要小于等于 $v_1$ ，只被矩形 2 包括的点需要小于等于 $v_2$ ，同时被两者包括的点需要小于等于 $\min\{v1,v2\}$ ．除此之外，还需要满足矩形 1 内存在 $v_1$ ，矩形 2 内存在 $v_2$ ．这需要怎么处理呢？

定义满足上述不等条件的方案数为 $S$ ．即满足：

只被矩形 1 包括的点需要小于等于 $v_1$ ，只被矩形 2 包括的点需要小于等于 $v_2$ ，同时被两者包括的点需要小于等于 $\min\{v1,v2\}$ ．

关系的方案存在 $A_{\varnothing}$ 种．而不满足矩形 1 的相等关系（即矩形 1 内存在值等于 $v_1$ ）的有 $A_{\{1\}}$ 种（此时矩形 2 的相等关系可以满足，也可以不满足），不满足矩形 2 相等关系的有 $A_{\{2\}}$ 种．同时不满足两个矩形的相等关系的有 $A_{\{1,2\}}$ 种．则根据容斥的相关知识，存在答案 $tot$ 的表达式：

tot = A_{\varnothing} -A_{\{1\}}-A_{\{2\}}+A_{\{1,2\}}

将其扩展到 $n=10$ ，则若 $A_S$ 中， $S$ 的大小为偶数，则符号为正， $S$ 的大小为奇数，则符号位负，就可以使用 $2^n$ 项将答案计算出来．

计算一下时间复杂度：

$O(2^n)$ 用于遍历所有可能的 $A_S$ 中的 $S$
$O(hw)$ 用于遍历图
$O(n)$ 用于在确定 $A_S$ 的 $S$ 后计算答案

时间复杂度 $O(n2^nhw)$ ，需要优化．

观察到此题 $n$ 很小，而 $h,w$ 很大，当值域很大，但值的个数很小时，可以考虑离散化．

具体来说，依照限制矩形的左右端点和上下端点可以将整个网格划分成一个一个的小矩形，同时满足每一个矩形内部的所有点共享一个限制．

![[grid_paper.png]]

如上图的示意图，上图中，有两个限制矩形（标为红色），依照这些矩形的边框，绿色实线将网格图分成了 9 块，每一块中的取值限制都是相同的．

具体来说，子集枚举所有可能的集合，对于每一个集合 $s$ ，尝试计算出 $A_s$ ，计算时，对于每一块，我们可以通过上面的研究计算出这一块的取值上限，然后使用快速幂计算取值上限的面积次方，加和即为 $A_s$ ，再通过容斥公式计算出最后的答案．

小技巧：离散化

离散化常用来解决值域很大，但值数很小，且只关心数与数之间相对关系的问题．离散化将值转换为该值在所有值中排名，以此减小值域．

本题用到的离散化将相同限制区域合并在一起，一同计算，这也属于离散化中的一种．

标程

1
#include <bits/stdc++.h>
2
#define int long long
3
typedef long long ll;
4
using namespace std;
5
const int MOD = 1'000'000'007;
6
const int N = 50;
7
int h, w, m, n;
8
int lx[N], ly[N], rx[N], ry[N], v[N], a[N][N], tx[N], ty[N];
9
int cntx, cnty;
10
ll ans;
11

12
int fastpow(int a, int p) {
13
    ll now = a, ans = 1;
14
    while (p > 0) {
15
        if (p & 1) {
16
            (ans *= now) %= MOD;
17
        }
18
        (now *= now) %= MOD;
19
        p >>= 1;
20
    }
21
    return ans;
22
}
23

24
void solve() {
25
    ans = 0;
26
    cntx = cnty = 0;
27
    cin >> h >> w >> m >> n;
28
    tx[++cntx] = 1, tx[++cntx] = h + 1;
29
    ty[++cnty] = 1, ty[++cnty] = w + 1;
30
    for (int i = 1; i <= n; i++) {
31
        cin >> lx[i] >> ly[i] >> rx[i] >> ry[i] >> v[i];
32
        tx[++cntx] = lx[i];
33
        tx[++cntx] = rx[i] + 1;
34
        ty[++cnty] = ly[i];
35
        ty[++cnty] = ry[i] + 1;
36
    }
37
    // 离散化
38
    sort(tx + 1, tx + cntx + 1);
39
    sort(ty + 1, ty + cnty + 1);
40
    int nx = unique(tx + 1, tx + cntx + 1) - tx - 1;
41
    int ny = unique(ty + 1, ty + cnty + 1) - ty - 1;
42
    for (int i = 1; i <= n; i++) {
43
        lx[i] = lower_bound(tx + 1, tx + nx + 1, lx[i]) - tx;
44
        rx[i] = lower_bound(tx + 1, tx + nx + 1, rx[i] + 1) - tx;
45
        ly[i] = lower_bound(ty + 1, ty + ny + 1, ly[i]) - ty;
46
        ry[i] = lower_bound(ty + 1, ty + ny + 1, ry[i] + 1) - ty;
47
    }
48
    // 进行容斥，mask 位上为 0，表不钦定，否则表钦定不能有 v_i
49
    for (int mask = 0; mask < (1 << n); mask++) {
50
        // 先默认每一个小矩形都没有限制，可以取到 [1,m]
51
        for (int i = 1; i < nx; i++) {
52
            for (int j = 1; j < ny; j++) {
53
                a[i][j] = m;
54
            }
55
        }
56
        // 对于题中提到的小矩形，我们将其限制为 v_i / v_i-1
57
        for (int i = 1; i <= n; i++) {
58
            // 现在正在处理第 i 个矩形
59
            for (int x = lx[i]; x < rx[i]; x++) {
60
                for (int y = ly[i]; y < ry[i]; y++) {
61
                    // 对于在第 i 个矩形内部的点(x,y)，更新其上限
62
                    if ((1 << (i - 1)) & mask) {
63
                        // 对应位是 1，被钦定不能有 v_i
64
                        // 因此上限是 v_i-1
65
                        a[x][y] = min(a[x][y], v[i] - 1);
66
                    } else {
67
                        // 没有钦定，随意
68
                        a[x][y] = min(a[x][y], v[i]);
69
                    }
70
                }
71
            }
72
        }
73
        ll tot = 1;
74
        // 对于上述限制，计算结果
75
        for (int x = 1; x < nx; x++) {
76
            for (int y = 1; y < ny; y++) {
77
                ll area = 1ll * (tx[x + 1] - tx[x]) * (ty[y + 1] - ty[y]);
78
                tot = 1ll * tot * fastpow(a[x][y], area) % MOD;
79
            }
80
        }
81
        if (__builtin_popcount(mask) & 1) {
82
            tot = -tot;
83
        }
84
        (ans += (tot + MOD) % MOD) %= MOD;
85
    }
86
    cout << ans << endl;
87
}
88

89
signed main() {
90
    ios::sync_with_stdio(false);
91
    cin.tie(0);
92
    cout.tie(0);
93
    int T;
94
    cin >> T;
95
    while (T--) {
96
        solve();
97
    }
98
    return 0;
99
}

音乐

音乐

P3813 矩阵填数#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

文章分享

音乐

安吉D16 T3

P3813 矩阵填数#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

文章分享