「Matrix」矩阵

形式化题目

给定 $M \times N$ 的 01 矩阵 $G$ 和 $Q$ 个 $A \times B$ 的 01 矩阵 $P_1, \dots, P_Q$ ，对每个 $P_k$ 判断：是否存在位置 $(i, j)$ （ $1 \leqslant i \leqslant M-A+1$ ， $1 \leqslant j \leqslant N-B+1$ ），使得对所有 $0 \leqslant r < A$ 、 $0 \leqslant c < B$ 都有 $G[i+r][j+c] = P_k[r][c]$ 。存在输出 1，否则输出 0。

$A \leqslant 100$ ， $M, N, B \leqslant 1000$ ， $Q \leqslant 1000$ 。

样例中询问矩阵为 $2 \times 2$ 。以第一个询问 $\begin{smallmatrix}11\\00\end{smallmatrix}$ 为例：它出现在原矩阵第 $1 \sim 2$ 行、第 $1 \sim 2$ 列，输出 1。下面用这个 $3 \times 3$ 原矩阵演示正解的两个核心量怎么算。

原矩阵每行可以看成一个二进制数，“行内长度为 $B$ 的窗口”就是连续 $B$ 列拼成的 $B$ 位二进制值。取 $B = 2$ ，三行的窗口值为：

行（二进制）	窗口 $[1,2]$	窗口 $[2,3]$
`111` = 7	`11` = 3	`11` = 3
`000` = 0	`00` = 0	`00` = 0
`111` = 7	`11` = 3	`11` = 3

把每个 $B$ 位窗口当作一个"字符"，一个 $A \times B$ 子块又可按 $2^B$ 进制折叠成一个整数。观察重点：第一张表说明"行内取窗口"是精确的位运算；下面会看到"竖向折叠"如何把 $A$ 行压成一个可滑动维护的指纹。

暴力解法

思路

对每个询问，枚举原矩阵所有 $(M-A+1)(N-B+1)$ 个左上角位置，逐格比较 $A \times B$ 个字符。最坏 $O(Q \cdot M \cdot N \cdot A \cdot B) \approx 10^{16}$ ，完全不可行。它的价值在于暴露瓶颈：每次"子矩阵是否相等"的判断都要 $O(AB)$ 。只要能把任意子矩阵压成一个可 $O(1)$ 查询的指纹，问题就解决了。

代码

暴力层不单独给出代码（本题按 Python 教学流程只保留正解 main.py，暴力仅作推导起点）；完整实现见下方正解。

复杂度

时间 $O(QMNAB)$ ，空间 $O(1)$ 。

瓶颈

单次比较 $O(AB)$ ，且这些比较对每个询问都要从头再来——询问矩阵是已知的，应当预先算好指纹放进集合，把问题反转成"原矩阵的每个子块，指纹在不在集合里"。

正解

思路

第一步：把矩阵匹配变成整数匹配。 一个 $A \times B$ 的 01 矩阵按行主序拼起来就是一个 $A \cdot B$ 位的 01 串，也就是一个整数。两个子矩阵相同当且仅当位串相同。于是对每个询问矩阵算出指纹，放进哈希表；再枚举原矩阵每个 $A \times B$ 子块的指纹去查表。

第二步：行内窗口用精确位串。 Python 里一行 0/1 字符串 int(s, 2) 就是一个大整数（左端在高位）。第 $c$ 列开始的 $B$ 位窗口值是

\left\lfloor \frac{v}{2^{N-c-B}} \right\rfloor \bmod 2^B,

代码里写成 (v >> (n - c - b)) & ((1 << b) - 1)。这是精确值，行内不引入任何哈希碰撞。 $M$ 行全部预处理出 $(N-B+1)$ 个窗口值，共 $O(MN)$ 次大整数移位（按机器字并行，实际约 $MN \cdot B/64$ 字操作）。

第三步：竖向 $2^B$ 进制折叠 + 滑动。 设第 $r$ 行第 $c$ 列窗口值为 $f_r[c]$ ，把 $A$ 行拼成位串等于在 $2^B$ 进制下展开（顶行在高位，与询问位串的高位对齐）：

H_r[c] = \sum_{k=0}^{A-1} f_{r-A+1+k}[c] \cdot (2^B)^{A-1-k} \pmod{2^{61}-1}.

对 Mersenne 素数 $2^{61}-1$ 取模防止大整数爆炸。底行下移一行时， $H$ 的变化只有"顶行移除、底行移入"，每列 $O(1)$ ：

H_{r}[c] = \bigl(H_{r-1}[c] - f_{r-A}[c] \cdot (2^B)^{A-1}\bigr) \cdot 2^B + f_{r}[c].

下面用样例（ $A=B=2$ ，取前两行、第 $1$ 列窗口）对照"折叠"与"真实位串"的关系：

子块	各行窗口值	$2^2$ 进制折叠 $f_{\text{顶}} \cdot 4 + f_{\text{底}}$	按行主序拼出的位串
$\begin{smallmatrix}11\\00\end{smallmatrix}$	$3,\ 0$	$3 \cdot 4 + 0 = 12$	`1100` = 12
$\begin{smallmatrix}00\\11\end{smallmatrix}$	$0,\ 3$	$0 \cdot 4 + 3 = 3$	`0011` = 3

观察重点：折叠值（第 3 列）与真实位串值（第 4 列）在不取模时完全相等——这正是"折叠 = 行主序拼接"的含义；取模后只损失极小概率的等值关系（碰撞概率 $\approx 10^9 / 2^{61} \approx 4 \times 10^{-10}$ ，可忽略，本题本身即"字符串 hash"类数据）。上表同时解释了为什么顶行的权是 $(2^B)^{A-1}$ ：它对应位串里最高的那 $B$ 位。

第四步：查询。 逐列拿 $H_r[c]$ 查询问指纹哈希表，命中则该询问所有下标都记 1。询问之间可能出现重复矩阵，按"矩阵原文"分桶去重，一次判定回填多个下标。

两个特判： $A > M$ 或 $B > N$ 时任何子块都不存在，直接全 0； $A = 1$ 时没有竖向折叠，退化为"每行窗口值放进集合，查询问指纹是否在集合里"。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#!/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-01 12:10
# update_at: 2026-10-01 12:10

import sys

MOD = (1 << 61) - 1  # Mersenne 素数：竖向折叠在 2^b 进制下对它取模（数据随机，单哈希足够）


def row_hashes(s: str, w: int) -> list[int]:
    """一行里所有长度为 w 的窗口，各拼成 w 位二进制整数指纹（精确值）。"""
    bits = int(s, 2)  # 整行读成一个二进制大整数，左端在高位
    full = (1 << w) - 1
    n = len(s)
    # 第 c 列的窗口 = (整行 >> (n - c - w)) 的低 w 位
    return [(bits >> (n - c - w)) & full for c in range(n - w + 1)]


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    m, n, a, b = (int(next(it)) for _ in range(4))
    rows = [next(it).decode() for _ in range(m)]        # 原矩阵 M 行字符串
    q = int(next(it))

    # 每个询问读 A 行、每行 B 列，按行主序拼成一个位串；重复矩阵去重后共享一次判定
    queries: dict[str, list[int]] = {}
    for i in range(q):
        queries.setdefault(''.join(next(it).decode() for _ in range(a)), []).append(i)
    q_hashes = {int(s, 2) % MOD: s for s in queries}    # 指纹 → 询问矩阵原文

    ans = [0] * q
    if a <= m and b <= n:                               # 询问比原矩阵还大时必然找不到
        fold = [[h % MOD for h in row_hashes(s, b)] for s in rows]  # 每行窗口指纹（mod 后）
        B = (1 << b) % MOD                              # 竖向折叠的进制 2^b
        if a == 1:                                      # 单行没有竖向折叠，直接查行内窗口
            table = set()
            for s in rows:
                table.update(h % MOD for h in row_hashes(s, b))
            for h, s in q_hashes.items():
                if h in table:
                    for i in queries[s]:
                        ans[i] = 1
        else:
            ncol = n - b + 1
            # H[c] = 以当前行为底的 a 行窗口在列 c 的指纹：
            # sum(第 r-k 行窗口指纹 * B^k)，顶行权 B^(a-1)（与询问位串的高位对齐）
            H = [0] * ncol
            for i in range(a - 1, -1, -1):
                pw = pow(B, a - 1 - i, MOD)
                Hi = fold[i]
                H = [(h + r * pw) % MOD for h, r in zip(H, Hi)]
            top_pow = pow(B, a - 1, MOD)                # 滑出行指纹的权
            for r in range(a - 1, m):
                if r > a - 1:                           # 底行滑入第 r 行、顶行滑出第 r-a 行
                    out_row, in_row = fold[r - a], fold[r]
                    H = [((h - o * top_pow) * B + i_) % MOD
                         for h, o, i_ in zip(H, out_row, in_row)]
                for c, h in enumerate(H):               # 逐列查指纹集合
                    s = q_hashes.get(h)
                    if s is not None:
                        for i in queries[s]:
                            ans[i] = 1

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167/**
 * 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-06 16:31
 * update_at: 2026-10-06 16:32
 */
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <cstddef>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 1005;                  // M、N 的上限
const ull MOD = (1ULL << 61) - 1;       // Mersenne 素数 2^61-1，二维哈希取模
const int BUFSZ = 1 << 20;              // 快速读入缓冲区大小

ll m, n, a, b, q;                       // 原矩阵行数、列数，询问矩阵行数、列数，询问个数
string grid[MAXN];                      // 原矩阵每一行（01 串）
ull rowhash[MAXN][MAXN];                // rowhash[i][j]：第 i 行第 j 列起长度为 b 的窗口指纹
ull pw2[2 * MAXN];                      // pw2[k] = 2^k mod MOD
ull H[MAXN];                            // H[j]：以当前行为底的 a 行窗口在第 j 列的指纹
map<ull, vector<int> > query_group;     // 询问指纹 -> 具有该指纹的询问下标列表（去重）
int ans[MAXN];                          // ans[i]：第 i 个询问的答案

char inbuf[BUFSZ];                      // 输入缓冲区
int inpos = 0, inlen = 0;

// 从缓冲区读入一个字符，缓冲区空时补读一块
inline char next_char() {
    if (inpos == inlen) {
        inlen = (int)fread(inbuf, 1, BUFSZ, stdin);
        inpos = 0;
        if (inlen == 0) return '\0';
    }
    return inbuf[inpos++];
}

// 读入一个非负整数
ll read_int() {
    char c = next_char();
    while (c < '0' || c > '9') c = next_char();
    ll x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = next_char();
    }
    return x;
}

// 2^61-1 下的乘法，用 __int128 承接中间结果防止溢出
ull mul_mod(ull x, ull y) {
    return (ull)((unsigned __int128)x * y % MOD);
}

// (x - y) mod MOD
ull sub_mod(ull x, ull y) {
    return x >= y ? x - y : x + MOD - y;
}

// 读入长度为 len 的 01 串（跳过空白），返回其按位拼成的整数 mod MOD
ull read_row_hash(ll len) {
    ull h = 0;
    ll done = 0;
    while (done < len) {
        ll take = len - done;
        if (take > 30) take = 30;       // 每 30 位成块，减少取模次数
        ull block = 0;
        for (ll k = 0; k < take; k++) {
            char c = next_char();
            while (c < '0' || c > '1') c = next_char();
            block = block * 2 + (c - '0');
        }
        h = (mul_mod(h, pw2[take]) + block) % MOD;
        done += take;
    }
    return h;
}

// 读入 q 个询问矩阵，各自按行主序折叠成一个指纹，相同指纹的询问合并到一组
void read_queries() {
    q = read_int();
    for (int i = 1; i <= q; i++) {
        ull h = 0;
        for (ll r = 1; r <= a; r++) {
            ull rowval = read_row_hash(b);  // 这一行 b 个字符拼成的 b 位整数
            h = (mul_mod(h, pw2[b]) + rowval) % MOD;
        }
        query_group[h].push_back(i);
    }
}

int main() {
    m = read_int();
    n = read_int();
    a = read_int();
    b = read_int();
    for (ll i = 1; i <= m; i++) {
        grid[i].reserve(n);
        for (ll j = 0; j < n; j++) {
            char c = next_char();
            while (c < '0' || c > '1') c = next_char();
            grid[i].push_back(c);
        }
    }

    pw2[0] = 1;
    for (int k = 1; k < 2 * MAXN; k++) pw2[k] = pw2[k - 1] * 2 % MOD;

    read_queries();

    if (a > m || b > n) {               // 询问矩阵比原矩阵还大，任何位置都放不下
        for (int i = 1; i <= q; i++) printf("0\n");
        return 0;
    }

    ll ncol = n - b + 1;                // 每行横向长度为 b 的窗口个数
    // 第一步：每行用滑动窗口求出所有 b 位窗口指纹
    for (ll i = 1; i <= m; i++) {
        ull val = 0;
        for (ll c = 0; c < b; c++) val = (val * 2 + (grid[i][c] - '0')) % MOD;
        rowhash[i][1] = val;
        for (ll j = 1; j < ncol; j++) {
            ull del = (grid[i][j - 1] == '1') ? pw2[b - 1] : 0; // 左端最高位
            ull mid = sub_mod(rowhash[i][j], del);
            rowhash[i][j + 1] = (mid * 2 + (grid[i][j + b - 1] - '0')) % MOD;
        }
    }

    // 第二步：竖向按 2^b 进制折叠，顶行权最大；滑动时每列 O(1) 维护
    ull pwB = pw2[b];
    ull pwTop = 1;                      // 顶行的权 pwB^(a-1)
    for (ll k = 1; k <= a - 1; k++) pwTop = mul_mod(pwTop, pwB);

    for (ll j = 1; j <= ncol; j++) {
        ull h = 0;
        for (ll i = 1; i <= a; i++) h = (mul_mod(h, pwB) + rowhash[i][j]) % MOD;
        H[j] = h;
    }

    for (ll r = a; r <= m; r++) {       // r 为当前 a×b 子矩阵的底行
        if (r > a) {
            ll out = r - a;             // 滑出的行
            ll in = r;                  // 滑入的行
            for (ll j = 1; j <= ncol; j++) {
                ull outv = mul_mod(rowhash[out][j], pwTop);
                ull mid = sub_mod(H[j], outv);
                H[j] = (mul_mod(mid, pwB) + rowhash[in][j]) % MOD;
            }
        }
        for (ll j = 1; j <= ncol; j++) {
            map<ull, vector<int> >::iterator it = query_group.find(H[j]);
            if (it != query_group.end()) {
                for (size_t t = 0; t < it->second.size(); t++) ans[it->second[t]] = 1;
                query_group.erase(it);  // 该指纹已命中，后续无需再查
            }
        }
        if (query_group.empty()) break; // 所有询问都已找到
    }

    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}

复杂度

时间：预处理 $O(MN)$ ，滑动枚举 $O\bigl((M-A+1)(N-B+1)\bigr)$ ，询问读入 $O(QAB)$ 位串操作，总计 $O(MN + QAB)$ ，与 C++ 二维哈希同阶。实测 $M=N=1000$ 的极限数据单点 0.35s（Python 侧宽裕；大整数移位/取模按机器字并行是 Python 的加分项）。
空间：fold 存 $M \times (N-B+1)$ 个指纹， $O(MN)$ ；实测峰值约 58MB，在 128MB 限内。

总结

二维匹配的标准思路：把二维模式压成一维指纹，"文本侧枚举 + 哈希查询"替代逐格比较。
本题的实现亮点是不对称哈希：横向窗口在 Python 里用大整数移位精确取出（零碰撞），只有竖向拼接需要多项式哈希（模 $2^{61}-1$ 滑动维护）。
询问侧先算指纹入集合，把"每个询问扫一遍原矩阵"反转成"原矩阵子块查一次表"， $Q$ 倍的开销被合并进一个哈希表。

图示解析

一趟滑动的完整视图

以样例前两行为底行（ $r=2$ ，即第 2 行）为例，展示 $H$ 从"初始化"到"查表"的过程：

步骤	状态（列 $c=1 \to c=2$ ）
读完第 1 行	$H = [\,3 \cdot 4,\ 3 \cdot 4\,] = [12,\ 12]$ （顶行权 $4$ ）
读完第 2 行	$H = [12 + 0,\ 12 + 0] = [12,\ 12]$ （底行权 $1$ ）
查表	$12 \in \{\text{询问指纹}\}$ ？命中 $\begin{smallmatrix}11\\00\end{smallmatrix}$ → 输出 `1`
底行滑到第 3 行	$H = [(12 - 3 \cdot 4) \cdot 4 + 3,\ \dots] = [3,\ 3]$ ，对应 $\begin{smallmatrix}00\\11\end{smallmatrix}$

观察重点：第二行初始化后 $H = [12, 12]$ 恰是子块 $\begin{smallmatrix}11\\00\end{smallmatrix}$ 两个横向位置的位串值；滑动一步后变成 $[3, 3]$ ，对应 $\begin{smallmatrix}00\\11\end{smallmatrix}$ ——"移除顶行 × 滑入底行"每列只做一次乘加，这就是整个算法 $O(MN)$ 的来源。真实数据里 $A$ 可达 100，若不滑动而每次重算折叠，复杂度会退回 $O(MNAB)$ ，与暴力同阶。

「Matrix」 矩阵

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结

图示解析

一趟滑动的完整视图