AtCoder Beginner Contest 445 题解

for-each2026年8月18日大约 21 分钟

AtCoder Beginner Contest 445 题解

项目	内容
比赛时间	2026-02-14
比赛链接	https://atcoder.jp/contests/abc445
题目数量	A–G 共 7 题

比赛概览

本场 ABC 445 整体难度中等偏上。A、B 是纯粹的送分题，C 是在"只前进不后退"的函数图上从后往前倒推的 DP；D 是一个"断头台切分"（guillotine cut）的贪心构造题；E 结合质因数分解与"最大/次大指数"来处理 Lcm；F 是 min-plus 半环上的矩阵快速幂；G 是压轴题，需要把问题建模成二分图最大独立集，再用最大流求解。E、F、G 三题区分度明显，其中 G 的综合性强（构造二染色 + 网络流重建答案），最值得重点掌握。

A - Strong Word

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_a

题目大意

给定一个长度不小于 2、由小写英文字母构成的字符串 $S$ ，判断 $S$ 的第一个字符和最后一个字符是否相同。相同输出 Yes，否则输出 No。

思路

这是一道签到题。直接取出首字符与尾字符比较即可，不需要任何额外处理。

需要注意的边界情况很少，唯一的细节是：

长度最小为 2，所以 front() 与 back() 永远不会指向同一个字符，比较结果只取决于这两个字符本身是否相等；
长度为 2 时同样成立（例如 "aa" 输出 Yes，"ab" 输出 No）。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string S;
    cin >> S;
    cout << (S.front() == S.back() ? "Yes" : "No") << '\n';
    return 0;
}

官方题解同样给出了 Python 版本：

S = input()
if S[0] == S[-1]:
    print("Yes")
else:
    print("No")

复杂度分析

时间复杂度： $O(|S|)$ （读入字符串）
空间复杂度： $O(|S|)$ （存储字符串）

B - Center Alignment

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_b

题目大意

给定 $N$ 个长度均为奇数的字符串 $S_1, S_2, \dots, S_N$ 。设 $m$ 为其中最长的字符串长度。对每个 $i$ ，构造长度为 $m$ 的字符串 $T_i$ ：在 $S_i$ 的左右两侧各加 $k$ 个 .，其中 $k$ 为非负整数，使得最终长度恰好为 $m$ 。按顺序输出 $T_1, \dots, T_N$ 。

思路

因为所有 $S_i$ 的长度都是奇数，而最长长度 $m$ 也是奇数，所以对任意 $i$ ， $m - |S_i|$ 是奇数减奇数，必为偶数，可以平均分到左右两边。

于是取

k = \frac{m - |S_i|}{2}

输出 $\underbrace{\cdots\cdots}_{k\text{ 个点}} + S_i + \underbrace{\cdots\cdots}_{k\text{ 个点}}$ 。

实现上直接使用 string(k, '.') 生成 $k$ 个点的串即可，不需要逐字符拼接。

易错点：注意 $k$ 是"左右各 $k$ 个"，不是总共 $k$ 个；先求出 $m$ 再统一处理所有字符串。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<string> S(N);
    int m = 0;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        m = max(m, (int)S[i].size());
    }

    for (int i = 0; i < N; i++) {
        int k = (m - (int)S[i].size()) / 2;
        cout << string(k, '.') << S[i] << string(k, '.') << '\n';
    }
    return 0;
}

官方题解同样给出了 Python 版本：

N = int(input())
S = [input() for _ in range(N)]
m = max(len(s) for s in S)
for s in S:
    k = (m - len(s)) // 2
    t = ("." * k) + s + ("." * k)
    print(t)

复杂度分析

时间复杂度： $O(N \cdot m)$ （输出总量为 $N \cdot m$ 个字符）
空间复杂度： $O(m)$ （除输入外，仅需构造单个长度至多 $m$ 的字符串）

C - Sugoroku Destination

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_c

题目大意

有 $N$ 个排成一列的格子 $1, 2, \dots, N$ 。格子 $i$ 上写着整数 $A_i$ （满足 $i \le A_i \le N$ ）。操作：记棋子所在格子上的数为 $x$ ，把棋子移动到格子 $x$ 。

对每个起点 $s = 1, 2, \dots, N$ ，问执行 $10^{100}$ 次操作后棋子所在的格子编号。

思路

关键观察 1：棋子只会向前走。

条件 $A_i \ge i$ 意味着每次移动后的格子编号不小于当前编号。于是可能形成的"环"只有自环，即满足 $A_i = i$ 的格子——棋子一旦到达这样的格子就再也动不了。

关键观察 2： $10^{100}$ 次操作等价于"一直走到不能再走"。

从格子 $i$ 出发，只要没有停在自环上，每一步编号至少增加 1，因此最多 $N - i$ 步内必然到达某个满足 $A_j = j$ 的自环格子。而 $N \le 5 \times 10^5 \ll 10^{100}$ ，所以 $10^{100}$ 次操作后棋子一定停在自环上。

朴素做法为什么不行： 对每个 $s$ 直接模拟，从 $s$ 出发要走 $O(N - s)$ 步，总复杂度 $O(N^2)$ ，会超时。

正解：从终点倒推的 DP。

设 $f(i)$ 为从格子 $i$ 出发最终停留的格子。由于 $A_i \ge i$ ：

若 $A_i = i$ ，则从 $i$ 出发第一步就停住，故 $f(i) = i$ ；
若 $A_i > i$ ，则第一步走到 $A_i$ ，之后的情况与从 $A_i$ 出发完全一致，故 $f(i) = f(A_i)$ 。

按 $i = N, N-1, \dots, 1$ 的倒序计算 $f(i)$ ：当 $A_i > i$ 时， $A_i$ 更大， $f(A_i)$ 必然已经算好。这样每个 $f(i)$ 只需 $O(1)$ 时间。

为什么正确： 由观察 1 保证函数图无环（除自环外），从任何起点出发的移动轨迹是一条不断前进的链，链的终点就是自环。倒序 DP 恰好沿链从尾部逐步求出每个点的"终点"，归纳可证。

注意本题输入用 0-based 下标实现时，判断条件变成 i == A[i]（读入时减 1），输出时再加 1。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N), f(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        --A[i];  // 转为 0-based
    }

    // 从大到小倒推
    for (int i = N - 1; i >= 0; i--) {
        f[i] = (i == A[i]) ? i : f[A[i]];
    }

    for (int i = 0; i < N; i++) {
        cout << f[i] + 1 << " \n"[i == N - 1];
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N)$
空间复杂度： $O(N)$

D - Reconstruct Chocolate

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_d

题目大意

桌面上有 $N$ 块巧克力，第 $i$ 块为 $h_i$ 行 $\times$ $w_i$ 列的矩形。已知它们是这样得到的：最初手中有一块 $H \times W$ 的整板，重复 $N-1$ 次"沿格线把手中那块竖直或水平切成两块，把其中一块放上桌、另一块留在手中"，最后把手中那块也放上桌。要求给出一种把 $N$ 块拼成一个 $H \times W$ 大矩形、且互不重叠、不可旋转的摆放方案（输出每块左上角坐标）。

思路

关键观察：好划分的"断头台"结构。

把"能由上述过程得到的一组块"称为一个好划分。设当前剩余矩形的尺寸为 $H' \times W'$ ，则一个好划分满足三条性质：

(a) 其中必有一块，其高度为 $H'$ 或宽度为 $W'$ ；
(b) 若其中有一块为 $H' \times t$ ，则去掉它后剩下的块构成一个 $H' \times (W'-t)$ 的好划分；
(c) 对称地，若有一块为 $t \times W'$ ，则剩下的块构成一个 $(H'-t) \times W'$ 的好划分。

性质 (a) 是显然的：第一步放上桌的那块就与整板共一条边（高为 $H$ 或宽为 $W$ ）。

性质 (b) 的证明：高度为 $H'$ 的块只可能产生于对"手中仍为整高 $H'$ "的板的竖切；一旦在手中做过横切，手中块的高度就严格变小，再也切不出高度为 $H'$ 的块。因此所有高度为 $H'$ 的块都在前几次操作中产生。交换这些块的放下顺序不影响最终块的集合，于是可以把任意一块 $H' \times t$ 当作第一块放下的，剩下的块恰好拼成一个 $H' \times (W'-t)$ 的矩形，且递归地是一个好划分。性质 (c) 同理。

贪心算法：

维护"当前剩余空白矩形"，它始终锚定大矩形的左上角，尺寸记为 $H' \times W'$ 。重复 $N$ 次：

由性质 (a)，一定存在一块未放的高为 $H'$ 或宽为 $W'$ 的巧克力；
取这样一块，放在剩余矩形的右下角：
- 若其高为 $H'$ ，则放在 $(1,\, W'-w+1)$ ，随后 $W' \leftarrow W' - w$ ；
- 若其宽为 $W'$ ，则放在 $(H'-h+1,\, 1)$ ，随后 $H' \leftarrow H' - h$ ；
由性质 (b)(c)，剩下的未放块仍然是当前剩余矩形的一个好划分，归纳保证过程能继续，直到放完。

由于剩余矩形始终锚定左上角，第 $i$ 块的绝对坐标统一为

x_i = H' - h_i + 1, \qquad y_i = W' - w_i + 1

实现： 把块分别按 $h_i$ 降序、 $w_i$ 降序排序，各维护一个指针并跳过已放置的块。每次检查"未放块中高度最大者"是否等于当前 $H'$ ：若是则取它，否则取"宽度最大者"（由性质 (a) 其宽度必等于当前 $W'$ ）。排序 $O(N\log N)$ ，放置过程每个指针单调推进，总共 $O(N)$ 。

注意：数据保证输入一定可以由题目过程得到，所以上述"总存在可放的块"的假设始终成立；若输入不合法则该贪心不适用。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long H, W;
    int N;
    cin >> H >> W >> N;
    vector<int> h(N), w(N);
    for (int i = 0; i < N; i++) cin >> h[i] >> w[i];

    // 按高度降序、按宽度降序分别排序
    vector<int> ordH(N), ordW(N);
    iota(ordH.begin(), ordH.end(), 0);
    iota(ordW.begin(), ordW.end(), 0);
    sort(ordH.begin(), ordH.end(), [&](int x, int y) { return h[x] > h[y]; });
    sort(ordW.begin(), ordW.end(), [&](int x, int y) { return w[x] > w[y]; });

    vector<int> ansX(N), ansY(N);
    vector<char> used(N, 0);
    int pH = 0, pW = 0;

    for (int step = 0; step < N; step++) {
        while (used[ordH[pH]]) pH++;
        while (used[ordW[pW]]) pW++;

        // 若当前最大未用高度等于 H，取它；否则取宽度等于 W 的块
        int i;
        if (h[ordH[pH]] == H) {
            i = ordH[pH];
        } else {
            i = ordW[pW];
        }

        // 放在剩余矩形的右下角
        ansX[i] = H - h[i] + 1;
        ansY[i] = W - w[i] + 1;
        used[i] = 1;

        if (h[i] == H) W -= w[i];
        else           H -= h[i];
    }

    for (int i = 0; i < N; i++) {
        cout << ansX[i] << " " << ansY[i] << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$ （排序为瓶颈；放置过程为 $O(N)$ ）
空间复杂度： $O(N)$

E - Many LCMs

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_e

题目大意

给定正整数序列 $A = (A_1, \dots, A_N)$ 。对每个 $k$ ，求 $A$ 中除去 $A_k$ 后剩下 $N-1$ 个元素的 $\mathrm{lcm}$ 对 $998244353$ 取模的结果。有 $T$ 组数据，所有数据的 $N$ 之和不超过 $2\times 10^5$ ， $A_i \le 10^7$ 。

思路

关键转化：把 Lcm 用质因数指数表示。

对质数 $p$ ，记 $v_p(x)$ 为 $x$ 的质因数分解中 $p$ 的指数（ $p$ -adic 阶）。对一组数 $x_1,\dots,x_n$ 有

v_p\bigl(\mathrm{lcm}(x_1,\dots,x_n)\bigr) = \max_{1\le j\le n} v_p(x_j)

即 Lcm 的 $p$ 指数等于所有数 $p$ 指数的最大值。

设全局（所有 $A_1,\dots,A_N$ ）的 $p$ 指数按降序为 $e_1(p) \ge e_2(p) \ge \dots$ （即最大值与次大值）。那么"除去 $A_k$ 后的最大值"为：

若 $v_p(A_k) = e_1(p)$ 且 $A_k$ 是唯一达到最大值的项，则除去的恰好是最大者，结果降为次大值 $e_2(p)$ ；
否则，结果仍为 $e_1(p)$ 。

注意：如果有多项同时达到最大值 $e_1(p)$ ，那么 $e_2(p) = e_1(p)$ ，除去的项并不改变结果，此时"除以 $p^{e_1-e_2}$ "等于除以 $p^0=1$ ，自然正确。

算法流程：

求出每个 $A_i$ 的质因数分解；
对出现过的每个质数 $p$ ，统计全局最大值 $e_1(p)$ 与次大值 $e_2(p)$ ；
计算全局 $\mathrm{lcm} = L = \prod_p p^{e_1(p)}$ （在模意义下连乘）；
对每个 $k$ ：令 $L_k = L$ ；遍历 $A_k$ 的每个质因子 $p$ ，若 $v_p(A_k) = e_1(p)$ ，则

L_k \leftarrow L_k \cdot \left(p^{\,e_1(p)-e_2(p)}\right)^{-1} \pmod{998244353}

因为 $998244353$ 是质数，逆元可用费马小定理 $a^{-1} \equiv a^{p-2}$ 计算。

质因数分解的高效方法：

预处理线性筛（或埃氏筛），求出每个数的最小质因子 $\mathrm{lpf}[x]$ 。线性筛复杂度 $O(M)$ ，其中 $M = \max A_i \le 10^7$ 。然后分解每个 $x$ ：不断取 $p = \mathrm{lpf}[x]$ 并除尽，每步 $O(1)$ ，一个数至多分解 $O(\log x)$ 次。

为什么正确： 由上面的指数分析， $L_k$ 对每个质数 $p$ 的指数都恰为"除去 $A_k$ 后其余数 $p$ 指数最大值"，而不同质数之间互不影响，所以乘积正确。模运算下用逆元实现除法即可。

易错点：

只有当 $A_k$ 的指数等于全局最大值 $e_1(p)$ 时才需要"降指数"；若 $v_p(A_k) < e_1(p)$ ， $A_k$ 本来就不是该质数指数最大的项，除不除它结果一样；
$A_i$ 最大到 $10^7$ ，每个数不同质因子不超过 8 个（ $2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 > 10^7$ ），所以 map 的操作量很小。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

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

    int T;
    cin >> T;
    vector<vector<int>> cases(T);
    int maxA = 0;
    for (int t = 0; t < T; t++) {
        int N;
        cin >> N;
        cases[t].resize(N);
        for (int i = 0; i < N; i++) {
            cin >> cases[t][i];
            maxA = max(maxA, cases[t][i]);
        }
    }

    // 线性筛：lpf[x] = x 的最小质因子
    vector<int> lpf(maxA + 1, 0), primes;
    for (int x = 2; x <= maxA; x++) {
        if (lpf[x] == 0) {
            lpf[x] = x;
            primes.push_back(x);
        }
        for (int p : primes) {
            if ((ll)p * x > maxA || p > lpf[x]) break;
            lpf[p * x] = p;
        }
    }

    for (auto& A : cases) {
        int N = (int)A.size();
        map<int, int> e1, e2;  // 每个质因子的全局最大、次大指数

        for (int x : A) {
            while (x > 1) {
                int p = lpf[x], e = 0;
                while (x % p == 0) { x /= p; e++; }
                if (e > e1[p]) { e2[p] = e1[p]; e1[p] = e; }
                else if (e > e2[p]) e2[p] = e;
            }
        }

        ll lcm = 1;
        map<int, ll> red;  // red[p] = p^(e1[p]-e2[p]) mod MOD
        for (auto& [p, e] : e1) {
            lcm = lcm * modpow(p, e) % MOD;
            red[p] = modpow(p, e - e2[p]);
        }

        for (int i = 0; i < N; i++) {
            ll ans = lcm;
            int x = A[i];
            while (x > 1) {
                int p = lpf[x], e = 0;
                while (x % p == 0) { x /= p; e++; }
                if (e == e1[p]) {
                    // A_i 是唯一达到 p 的最大指数的项，降为次大指数
                    ans = ans * modpow(red[p], MOD - 2) % MOD;
                }
            }
            cout << ans << " \n"[i + 1 == N];
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O(M + \sum_i \omega(A_i) \cdot \log \mathrm{MOD})$ ，其中 $M = \max A_i$ ， $\omega(x)$ 为 $x$ 的质因子个数（含重复），整体约为 $O(M + N\log M \log \mathrm{MOD})$ ；用 map 统计时再乘上对数因子
空间复杂度： $O(M)$ （线性筛数组）

F - Exactly K Steps 2

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_f

题目大意

给定一个 $N$ 个点的完全带权有向图，边 $i \to j$ 的权值为 $C_{i,j}$ （ $0 \le C_{i,j} \le 10^9$ ）。对每个起点 $s$ ，求"从 $s$ 出发走恰好 $K$ 条边再回到 $s$ "的闭合路径的最小总代价，其中 $K \le 10^9$ 。

思路

关键转化：min-plus 矩阵乘法。

设 $c^k_{i,j}$ 表示恰好走 $k$ 条边从 $i$ 到 $j$ 的最小总代价。显然 $c^1_{i,j} = C_{i,j}$ 。

若已知恰好 $a$ 步的代价矩阵 $c^a$ 和恰好 $b$ 步的代价矩阵 $c^b$ ，那么恰好 $a+b$ 步可以从 $i$ 先走 $a$ 步到某个中间点 $j$ ，再走 $b$ 步到 $k$ ，取所有 $j$ 的最小值：

c^{a+b}_{i,k} = \min_{1 \le j \le N} \left( c^a_{i,j} + c^b_{j,k} \right)

这正是矩阵乘法，只不过"乘法"变成了"加法"、"加法"变成了"取 $\min$ "——这就是 (min, +) 半环（也称热带半环）上的矩阵乘法：

(X \otimes Y)_{i,k} = \min_j (X_{i,j} + Y_{j,k})

用快速幂求 $c^K$ ：

在 (min, +) 半环上矩阵乘法满足结合律，所以可以直接套用快速幂。单位矩阵为

I_{i,j} = \begin{cases} 0 & i = j \\ +\infty & i \ne j \end{cases}

（走 0 步只能从 $i$ 到 $i$ ，代价为 0。）对 $C$ 做 $K$ 次"自乘"的二进制幂，最终矩阵的对角元 $c^K_{s,s}$ 就是答案。

为什么正确： 结合律保证了快速幂的正确性； $K$ 步路径在第 $K/2$ 步处被拆成两半的方式取遍所有 $j$ ，恰好覆盖所有 $K$ 步路径。由于所有边权非负且允许重复走同一条边，不存在"绕圈更省"的问题，恰 $K$ 步的最小值就是要求的值。

数值细节：

最大答案不超过 $K \cdot \max C_{i,j} \le 10^9 \times 10^9 = 10^{18}$ ，要用 64 位整数；
无穷大 $\mathrm{inf}$ 取一个比答案上限更大的值（例如 $4\times 10^{18}$ ），且 $\mathrm{inf} + \mathrm{inf}$ 仍不超过 long long 上限，不会溢出；
矩阵乘法 $O(N^3)$ ，快速幂约 $O(\log K)$ 次乘法， $N \le 100$ 时完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

// (min, +) 半环上的矩阵乘法
vector<vector<ll>> matMul(const vector<vector<ll>>& X, const vector<vector<ll>>& Y) {
    int n = (int)X.size();
    vector<vector<ll>> Z(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (X[i][j] == INF) continue;
            for (int k = 0; k < n; k++) {
                if (Y[j][k] != INF) {
                    Z[i][k] = min(Z[i][k], X[i][j] + Y[j][k]);
                }
            }
        }
    }
    return Z;
}

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

    int N;
    ll K;
    cin >> N >> K;

    vector<vector<ll>> C(N, vector<ll>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) cin >> C[i][j];

    // res：恰好 0 步的矩阵（单位元）
    vector<vector<ll>> res(N, vector<ll>(N, INF));
    for (int i = 0; i < N; i++) res[i][i] = 0;

    // 快速幂：res = C^K（min-plus 意义下）
    while (K > 0) {
        if (K & 1) res = matMul(res, C);
        C = matMul(C, C);
        K >>= 1;
    }

    for (int i = 0; i < N; i++) {
        cout << res[i][i] << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N^3 \log K)$
空间复杂度： $O(N^2)$

G - Knight Placement

题目链接：https://atcoder.jp/contests/abc445/tasks/abc445_g

题目大意

给定一个 $N \times N$ 的网格，部分格子是墙（#）、部分为空（.）。要在空格上尽可能多地放棋子，限制是：若在 $(i,j)$ 放棋子，则 $(i\pm A, j\pm B)$ 与 $(i\pm B, j\pm A)$ 这 8 个方向（在网格内时）都不能再放棋子。求最多能放多少个，并输出一种放法（空格放棋子记为 o）。

思路

第一步：建模为最大独立集

把每个空格当作一个顶点，若两个格子不能同时放棋子则连一条边。所求"最多放多少棋子"就是该图的最大独立集（maximum independent set）。

直接求一般图的最大独立集是 NP 困难的，但这里有一个关键性质：这个图是二分图。

第二步：证明图是二分图（构造二染色）

目标是给每个格子染黑/白两色，使得任意一对冲突的格子异色。

先给出直觉：令 $g = \gcd(A, B)$ ，把网格按 $g \times g$ 分块，块内同色，问题就化归到 $\gcd = 1$ 的情形。 $\gcd = 1$ 时：

若 $A, B$ 都为奇数，按行号奇偶染色（一次移动行号改变奇数，必然异色）；
若 $A, B$ 一奇一偶，按 $i+j$ 的奇偶染色（一次移动改变 $i+j$ 一个奇数，必然异色）。

而参考代码用一个统一公式实现同样的染色，下面给出严格的证明。

设 $t = v_2(A \mid B) = \min(v_2(A), v_2(B))$ ，即 $2^t$ 是 $A\mid B$ 的最低非零比特位（也就是 $2^t = (A\mid B) \,\&\, -(A\mid B)$ ）。定义染色

f(i,j) = \Bigl[ i \oplus \bigl( j \wedge (A \oplus B) \bigr) \text{ 的第 } t \text{ 个比特} \Bigr] \in \{0,1\}

（记号： $\oplus$ 为按位异或， $\wedge$ 为按位与， $[\cdot]$ 表示取该比特位的值。）

证明 $f$ 是合法染色。 记 $c = A \oplus B$ ， $A = 2^t\alpha,\ B = 2^t\beta$ 。由 $t$ 的定义， $\alpha, \beta$ 不全为偶数；且 $c$ 的第 $t$ 比特等于 $(\alpha \bmod 2) \oplus (\beta \bmod 2)$ 。

任意一步移动 $(\Delta i, \Delta j)$ 都满足 $\{\Delta i / 2^t,\ \Delta j/2^t\} = \{\pm\alpha,\ \pm\beta\}$ 。

$i$ 方向：加 $\Delta i$ 不改变 $i$ 的低 $t$ 位（无进位），第 $t$ 位的翻转量为 $\delta_i = (\Delta i / 2^t) \bmod 2$ 。
$j$ 方向： $(j\wedge c)$ $(j \land c)$ 的第 $t$ $t$ 位等于 $j$ $j$ 的第 $t$ $t$ 位与 $c$ $c$ 的第 $t$ $t$ 位的与。
- 若 $c$ 第 $t$ 位为 1，则 $j$ 方向第 $t$ 位的翻转量 $\delta_j = (\Delta j / 2^t) \bmod 2$ ；
- 若 $c$ 第 $t$ 位为 0，则 $j$ 方向贡献恒为 0。

分两种情况：

$c$ 第 $t$ 位为 0，即 $\alpha, \beta$ 均为奇数。此时无论移动是 $(\pm A,\pm B)$ 还是 $(\pm B,\pm A)$ ， $\delta_i = 1$ ，颜色翻转。
$c$ 第 $t$ 位为 1，即 $\alpha,\beta$ 一奇一偶。总翻转量为 $\delta_i \oplus \delta_j$ ：对 $(\pm A,\pm B)$ 是 $(\alpha + \beta) \bmod 2 = 1$ ，对 $(\pm B,\pm A)$ 是 $(\beta + \alpha) \bmod 2 = 1$ ，颜色翻转。

因此任何两个互斥的格子都异色，图为二分图。左右部即由 $f(i,j)$ 的值划分。

第三步：二分图最大独立集 = 最大流

由 König 定理，二分图的最大独立集大小满足

\text{最大独立集大小} = |V| - \text{最小点覆盖} = |V| - \text{最大匹配}

而最小点覆盖可以用最大流求出。建网络如下：

超级源 $s$ → 每个左部空格，容量 $1$ ；
每个右部空格 → 超级汇 $t$ ，容量 $1$ ；
每条冲突边，从左部端点连向右部端点，容量 $+\infty$ （保证最小割永远不会割断冲突边）。

最大流的值 = 最大匹配数 = 最小点覆盖数。

重建最大独立集： 跑完最大流后，在残余网络中从源 $s$ 出发做 BFS，记可达集合为 $S$ 。最小点覆盖为

(\text{左部中不在 } S \text{ 的点}) \cup (\text{右部中在 } S \text{ 的点})

最大独立集是点覆盖的补集，即

(\text{左部中在 } S \text{ 的点}) \cup (\text{右部中不在 } S \text{ 的点})

把这些点输出为 o，其余空格输出 .，墙输出 # 即可。

实现细节：

冲突方向只需枚举 4 个： $(A,B), (B,A), (-B,A), (-A,B)$ ，每个无序冲突对恰好被加入一次（其余 4 个方向会在另一端点枚举到）；
只用 $N \le 300$ ，网格点数 $\le 90000$ ，边数 $O(N^2)$ ，Dinic 算法在单位容量网络的复杂度为 $O(E\sqrt V) = O(N^3)$ ，完全可行；
若不使用 AtCoder Library，可以手写 Dinic（如下面的参考实现）；使用 atcoder::maxflow 的写法更短。冲突边容量取一个大数即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;

// 最大流（Dinic）
struct Dinic {
    struct Edge { int to, rev; ll cap; };
    vector<vector<Edge>> g;
    vector<int> level, it;
    Dinic(int n) : g(n), level(n), it(n) {}
    void add_edge(int u, int v, ll c) {
        g[u].push_back({v, (int)g[v].size(), c});
        g[v].push_back({u, (int)g[u].size() - 1, 0});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : g[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    ll dfs(int u, int t, ll f) {
        if (u == t) return f;
        for (int& i = it[u]; i < (int)g[u].size(); i++) {
            Edge& e = g[u][i];
            if (e.cap > 0 && level[u] < level[e.to]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    void max_flow(int s, int t) {
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (dfs(s, t, INF) > 0) {}
        }
    }
    // 残余网络中从 s 可达的点集
    vector<char> min_cut(int s) {
        vector<char> vis(g.size(), 0);
        queue<int> q;
        vis[s] = 1; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : g[u]) {
                if (e.cap > 0 && !vis[e.to]) {
                    vis[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
        return vis;
    }
};

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

    int N, A, B;
    cin >> N >> A >> B;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    // 二染色的统一公式：block = 2^t, 其中 t = v2(A|B)
    int block = (A | B) & -(A | B);
    auto side = [&](int i, int j) -> bool {
        return block & (i ^ (j & (A ^ B)));  // true = 左部
    };
    auto id = [&](int i, int j) { return 1 + i * N + j; };

    int SRC = 0, SNK = 1 + N * N;
    Dinic din(1 + N * N + 1);

    // 源/汇连接
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            if (S[i][j] != '.') continue;
            if (side(i, j)) din.add_edge(SRC, id(i, j), 1);
            else            din.add_edge(id(i, j), SNK, 1);
        }

    // 冲突边：只枚举 4 个方向，保证每条冲突边加入一次
    int dx[4] = {A, B, -B, -A};
    int dy[4] = {B, A, A, B};
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            if (S[i][j] != '.') continue;
            for (int d = 0; d < 4; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
                if (S[ni][nj] != '.') continue;
                if (side(i, j)) din.add_edge(id(i, j), id(ni, nj), INF);
                else            din.add_edge(id(ni, nj), id(i, j), INF);
            }
        }

    din.max_flow(SRC, SNK);
    auto cut = din.min_cut(SRC);  // cut[v] = 是否在残余网络中从源可达

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (S[i][j] == '#') { cout << '#'; continue; }
            if (side(i, j)) {
                cout << (cut[id(i, j)] ? 'o' : '.');  // 左部中在 S 的点
            } else {
                cout << (cut[id(i, j)] ? '.' : 'o');  // 右部中不在 S 的点
            }
        }
        cout << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N^3)$ （Dinic 在单位容量二分网络上的复杂度为 $O(E\sqrt V)$ ，其中 $V = O(N^2), E = O(N^2)$ ）
空间复杂度： $O(N^2)$ （网格、网络边）

（完）