AtCoder Beginner Contest 425 题解

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

AtCoder Beginner Contest 425 题解

项目	内容
比赛时间	2025-09-27
比赛链接	https://atcoder.jp/contests/abc425
题目数量	A–G 共 7 题

比赛概览

本场整体难度平缓递进：A、B 是纯入门题；C 是经典的"环形旋转 + 区间和"双指针/前缀和技巧题；D 是一道网格染色过程的模拟，关键观察是"每个格子至多被染黑一次"；E 需要把多重组合数在任意模数下用帕斯卡三角预处理求出来；F 是反向删除 + 状态压缩 DP，难点在于如何对相同的字符串序列去重；G 则是按最高位分治的递归题，把字典树（Trie）的思想展开成集合划分的递归式，思维含量最高。其中 E、F、G 三道题较有区分度，值得重点掌握。

A - Sigma Cubes

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_a

题目大意

给定正整数 $N$ （ $1\le N\le 10$ ），求 $\displaystyle\sum_{i=1}^{N}(-1)^i\times i^3$ 的值。

思路

这是纯粹的入门循环题。因为 $N$ 至多只有 $10$ ，直接用一个 for 循环累加即可：当 $i$ 为偶数时 $(-1)^i=1$ ，累加 $i^3$ ；当 $i$ 为奇数时 $(-1)^i=-1$ ，累减 $i^3$ 。这是最直观、最不易出错的做法。

顺便一提，本题还存在一个封闭形式公式：

\sum_{i=1}^{N}(-1)^i\times i^3=\frac{(-1)^N(4N^3+6N^2-1)+1}{8}.

它可以这样推导：设 $N=2m$ ，把相邻两项配对，

S_{2m}=\sum_{i=1}^{2m}(-1)^i i^3=\sum_{k=1}^{m}\left[(2k)^3-(2k-1)^3\right] =\sum_{k=1}^{m}(12k^2-6k+1)=m^2(4m+3),

而 $N=2m+1$ 时 $S_{2m+1}=S_{2m}-(2m+1)^3=-(m+1)^2(4m+1)$ 。把两种奇偶情况合并即可得到上面的公式。不过本题数据范围极小，直接循环是最佳选择；公式版本作为验证手段也很有用。注意 $N\le 10$ 时 $i^3\le 1000$ ，答案用 int 就够，但用 long long 更稳妥。

参考代码

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

int main() {
    int N;
    cin >> N;
    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 2 == 0) ans += 1LL * i * i * i;  // (-1)^i = +1
        else ans -= 1LL * i * i * i;             // (-1)^i = -1
    }
    cout << ans << endl;
    return 0;
}

官方题解还给出了基于封闭公式的一行 Python 实现（利用 Python 的 // 做精确整除，公式值恒为整数）：

N = int(input())
print(((-1) ** N * (4 * N**3 + 6 * N**2 - 1) + 1) // 8)

复杂度分析

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

B - Find Permutation 2

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_b

题目大意

给定长度为 $N$ 的序列 $A$ ，每个元素要么是 $-1$ ，要么是 $1\sim N$ 中的某个整数。问是否存在一个 $1\sim N$ 的排列 $P$ ，使得对每个满足 $A_i\neq -1$ 的位置都有 $P_i=A_i$ 。若存在，输出 Yes 并给出任意一个合法的 $P$ ；否则输出 No。 $N\le 10$ 。

思路

$N\le 10$ ，所以 $N!\le 3\,628\,800$ ，完全可以直接枚举所有排列。

具体做法：用 std::next_permutation 从 $(1,2,\ldots,N)$ 开始依次生成全部 $N!$ 个排列，对每个排列 $P$ 检查条件是否对全部 $i$ 成立。条件"若 $A_i\neq -1$ 则 $P_i=A_i$ "等价于逻辑表达式" $A_i=-1$ 或 $P_i=A_i$ "，写成 a[i] == -1 || p[i] == a[i] 即可，实现上非常简洁。

正确性：任何满足条件的 $P$ 必然是 $(1,\ldots,N)$ 的排列，而我们恰好枚举了所有排列，所以只要存在解就一定能枚举到；一旦找到就立即输出并终止程序，找不到则输出 No。若固定值之间存在冲突（例如同一个值出现在两个不同位置），自然不会有排列通过检查，枚举完就会输出 No，无需特判。

易错点：输出任意合法解即可，不需要字典序最小；注意固定值本身都在 $[1,N]$ 内，所以不存在"越界"的固定值。

参考代码

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> p(n);
    iota(p.begin(), p.end(), 1);  // p = (1, 2, ..., n)
    do {
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (a[i] != -1 && a[i] != p[i]) ok = false;
        }
        if (ok) {
            cout << "Yes\n";
            for (int i = 0; i < n; i++) {
                cout << p[i] << " \n"[i + 1 == n];
            }
            return 0;
        }
    } while (next_permutation(p.begin(), p.end()));

    cout << "No\n";
    return 0;
}

官方题解的 Python 版本（利用 itertools.permutations）：

from itertools import permutations

n = int(input())
a = list(map(int, input().split()))
for p in permutations([i + 1 for i in range(n)]):
    ok = True
    for i in range(n):
        ok &= a[i] == -1 or p[i] == a[i]
    if ok:
        print("Yes")
        print(*p)
        break
else:
    print("No")

复杂度分析

时间复杂度： $O(N!\cdot N)$ ，最坏约 $3.6\times 10^7$ 次基本操作
空间复杂度： $O(N)$

C - Rotate and Sum Query

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_c

题目大意

给定长度为 $N$ 的整数序列 $A$ ，按顺序处理 $Q$ 个操作，共两类：

1 c：把 $A$ 的第一个元素移到末尾，重复 $c$ 次（即整体左移 $c$ 位）；
2 l r：输出当前 $A_l+A_{l+1}+\cdots+A_r$ 。

$N,Q\le 2\times 10^5$ ， $A_i\le 10^9$ 。

思路

关键观察：左移操作并不需要真的改动数组。左移 $c$ 位等价于"把整个数组看作一个环形，起始下标向后移动 $c$ "。因此只要维护一个全局偏移量

C=\left(\sum \text{已执行所有操作 1 的 }c\right)\bmod N,

就能 $O(1)$ 知道当前数组的起点在原始数组中的位置。

为了能用前缀和回答区间查询，把 $A$ 复制两份拼成 $B=(A_1,\ldots,A_N,A_1,\ldots,A_N)$ （长度 $2N$ ）。由于 $0\le C<N$ ，当前数组恰好是 $B$ 中的连续一段

B_C,B_{C+1},\ldots,B_{C+N-1}.

具体地，当前数组的第 $p$ （ $1\le p\le N$ ）个元素就是 $B_{C+p-1}$ （下标从 $0$ 起）。于是操作 2 l r 的答案就是

\sum_{i=l}^{r}A_i=\sum_{i=l}^{r}B_{C+i-1}=S_{C+r}-S_{C+l-1},

其中 $S$ 是 $B$ 的前缀和， $S_j=\sum_{t=0}^{j-1}B_t$ 。由于 $C+r\le (N-1)+N=2N-1$ ，前缀和数组开 $2N+1$ 大小即可，不会越界。

为什么正确：所有左移只在"起点位置"上累积，而环形结构保证任何一次操作 1 后数组都仍是 $B$ 中长度 $N$ 的连续段；前缀和预处理一次后，区间求和只需两次减法，均为 $O(1)$ 。

易错点： $c$ 需要累积并取模；取模后偏移在 $[0,N-1]$ ，不会让下标越出 $B$ 的范围。另外 $A_i$ 可达 $10^9$ ，区间和要用 long long。

参考代码

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

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

    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    // B = A + A，pref 为 B 的前缀和
    vector<long long> pref(2 * n + 1, 0);
    for (int i = 0; i < 2 * n; i++) pref[i + 1] = pref[i] + a[i % n];

    long long shift = 0;  // 全局左移偏移量（对 n 取模后）
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int c;
            cin >> c;
            shift = (shift + c) % n;
        } else {
            int l, r;
            cin >> l >> r;
            // 当前数组第 p 个元素 = B[shift + p - 1]
            cout << pref[shift + r] - pref[shift + l - 1] << '\n';
        }
    }
    return 0;
}

官方题解给出的是基于后缀和的 Python 实现，思路等价：

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
for i in range(2 * n - 1, 0, -1):
    b[i - 1] += b[i]          # b[i] = 从 i 到末尾的后缀和
rui_c = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        rui_c = (rui_c + query[1]) % n
    else:
        l, r = query[1] - 1, query[2]
        print(b[l + rui_c] - b[r + rui_c])

复杂度分析

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

D - Ulam-Warburton Automaton

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_d

题目大意

有一个 $H\times W$ 的网格，初始某些格子为黑色（#）、其余为白色（.）。不断执行以下操作共 $10^{100}$ 次：设 $T$ 为所有"白色且恰好有 1 个黑色邻居"的格子的集合，把 $T$ 中所有格子同时染黑。求最终黑色格子的数量。 $HW\le 3\times 10^5$ 。

思路

关键观察 1：每个格子至多被染黑一次

格子只会由白变黑，不会由黑变白，因此每个格子在整个过程中至多进入一次 $T$ 。

关键观察 2：第 $i+1$ 步被染黑的格子必与第 $i$ 步被染黑的格子相邻

设格子 $x$ 在第 $t+1$ 步被染黑（即 $x\in T_{t+1}$ ）。在第 $t$ 步结束时， $x$ 是白色且恰好有一个黑色邻居 $y$ 。反证：假设 $y$ 在第 $t$ 步之前就已经是黑色（即 $y\notin T_t$ ）。

若在第 $t-1$ 步结束时 $x$ 恰好有一个黑色邻居，那么 $x$ 应该在第 $t$ 步就被染黑，与" $x$ 在第 $t+1$ 步才被染黑"矛盾；
若在第 $t-1$ 步结束时 $x$ 的黑色邻居数 $\ge 2$ ，由于黑色集合只增不减，第 $t$ 步结束时 $x$ 的黑色邻居数仍 $\ge 2$ ，这与"第 $t$ 步结束时 $x$ 恰好有 1 个黑色邻居"矛盾。

因此 $y$ 必然在第 $t$ 步刚被染黑，即 $y\in T_t$ 。

算法流程

由观察 2，求 $T_{t+1}$ 时只需检查 $T_t$ 中所有格子的四邻域即可，无需全图扫描。算法如下：

初始时扫描整个网格，把所有"白色且恰好有 1 个黑色邻居"的格子放入 $T$ （即 $T_1$ ）。
若 $T=\varnothing$ ，过程终止；否则把 $T$ 中所有格子染黑。
遍历 $T$ 中每个格子的四邻域：若某个邻居当前仍为白色，且恰好有 1 个黑色邻居，则放入新的集合 $T'$ 。
令 $T\gets T'$ ，回到第 2 步。

复杂度论证：集合 $T_1,T_2,\ldots$ 两两不交（每个格子只被染黑一次），所以 $\sum |T_i|\le HW$ 。每轮对 $T_i$ 中的每个格子检查常数个邻居，总检查次数是 $O(HW)$ 。由于每步至少染黑一个格子，过程至多 $HW$ 步就会停止，因此操作 $10^{100}$ 次与"一直操作到稳定"完全等价。

实现细节：

染黑 $T$ 之后再去检查邻居，保证"恰好 1 个黑色邻居"用的是最新状态；
因为"恰好 1 个黑邻居 + 邻接 $T$ "的条件已经保证每个新格子只可能被唯一的 $T$ 格子发现，理论上不会重复，但稳妥起见还是对 $T'$ 去重；
若初始就没有满足条件的白格（例如全白网格），答案就是初始黑格数。

参考代码

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

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

    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto &s : S) cin >> s;

    const int dx[4] = {1, 0, -1, 0};
    const int dy[4] = {0, 1, 0, -1};

    auto in = [&](int x, int y) { return 0 <= x && x < H && 0 <= y && y < W; };
    auto cnt = [&](int x, int y) {   // 统计 (x, y) 的黑色邻居数
        int c = 0;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (in(nx, ny) && S[nx][ny] == '#') c++;
        }
        return c;
    };

    vector<pair<int, int>> T;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (S[i][j] == '.' && cnt(i, j) == 1) T.push_back({i, j});

    while (!T.empty()) {
        for (auto [x, y] : T) S[x][y] = '#';          // 同时染黑
        vector<pair<int, int>> nT;
        for (auto [x, y] : T) {
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (in(nx, ny) && S[nx][ny] == '.' && cnt(nx, ny) == 1)
                    nT.push_back({nx, ny});
            }
        }
        sort(nT.begin(), nT.end());
        nT.erase(unique(nT.begin(), nT.end()), nT.end());
        T = nT;
    }

    long long ans = 0;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (S[i][j] == '#') ans++;
    cout << ans << endl;
    return 0;
}

官方题解的 Python 实现（不显式去重，逻辑相同）：

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

dxdy = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def in_grid(x, y):
    return 0 <= x < H and 0 <= y < W

def count(x, y):
    c = 0
    for dx, dy in dxdy:
        nx, ny = x + dx, y + dy
        if in_grid(nx, ny) and S[nx][ny] == "#":
            c += 1
    return c

for i in range(H * W):
    if i == 0:
        T = []
        for x in range(H):
            for y in range(W):
                if S[x][y] == "." and count(x, y) == 1:
                    T.append((x, y))
    else:
        nT = []
        for x, y in T:
            for dx, dy in dxdy:
                nx, ny = x + dx, y + dy
                if in_grid(nx, ny) and S[nx][ny] == "." and count(nx, ny) == 1:
                    nT.append((nx, ny))
        T = nT
    if len(T) == 0:
        break
    for x, y in T:
        S[x][y] = "#"

print(sum(row.count("#") for row in S))

复杂度分析

时间复杂度： $O(HW)$ （每个格子至多被检查常数次）
空间复杂度： $O(HW)$

E - Count Sequences 2

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_e

题目大意

$T$ 个测试用例，给定正整数 $N$ 与序列 $C=(C_1,\ldots,C_N)$ 。统计满足以下条件的正整数序列的个数，结果对给定的（不一定是素数的）模数 $M$ 取模：

序列的每个元素都在 $1\sim N$ 之间；
对每个 $i$ ，值 $i$ 在序列中恰好出现 $C_i$ 次。

约束： $\sum_{i=1}^N C_i\le 5000$ ， $M\le 10^9$ ，各用例 $N$ 之和 $\le 3\times 10^5$ 。

思路

问题转化：多重组合数

所有元素之和为 $S=\sum_i C_i$ 。一个满足条件的序列就是：先决定长度为 $S$ ，其中 $C_1$ 个位置放 $1$ 、 $C_2$ 个位置放 $2$ 、……、 $C_N$ 个位置放 $N$ 。这是经典的多重排列（multinomial coefficient）问题，答案是

\frac{S!}{C_1!\,C_2!\,\cdots\,C_N!}.

直接验证：样例 1 第一组 $C=(2,2)$ ， $S=4$ ，答案为 $4!/(2!2!)=6$ ，与样例一致。

关键技巧：化为二项式系数的乘积

多重组合数可以写成若干二项式系数的乘积：

\frac{S!}{C_1!C_2!\cdots C_N!} =\binom{C_1}{C_1}\binom{C_1+C_2}{C_2}\binom{C_1+C_2+C_3}{C_3}\cdots\binom{S}{C_N}.

（记 $S_i=\sum_{j=1}^i C_j$ ，则 $\binom{S_i}{C_i}=\dfrac{S_i!}{C_i!\,S_{i-1}!}$ ，逐项相乘后分子分母交错消去，只剩下 $S!/(\prod C_i!)$ 。）于是只需从左到右维护前缀和 $S_i$ ，每次乘上 $\binom{S_i}{C_i}$ 即可。

任意模数下的组合数：帕斯卡三角

$M$ 不一定是素数，因此不能用"阶乘 + 逆元"预处理组合数。但 $\sum C_i\le 5000$ ，可以直接用帕斯卡递推在模 $M$ 意义下预处理 $0\le k\le n\le 5000$ 的全部二项式系数：

\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.

该递推只涉及加法，对任意模数 $M$ 都成立，预处理后每个组合数可在 $O(1)$ 查询。每个测试用例只需 $O(N)$ 次乘法取模。

正确性：多重排列计数是基本组合结论；帕斯卡递推给出的 $\binom{n}{k}\bmod M$ 在 $n\le 5000$ 范围内覆盖了所有需要的查询（前缀和 $S_i\le S\le 5000$ ）。由于 $M\ge 2$ 且每个 $\binom{n}{k}<M\le 10^9$ ，表内元素用 int 存储即可，求和时注意用 long long 转存避免中间溢出。

易错点：表的第二维大小要开足（至少 $5001$ ）；ans 初始化为 $1$ ；每步 ans = ans * C[s][c] % M 中乘积可能接近 $10^{18}$ ，必须用 long long。

参考代码

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

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

    int T;
    long long M;
    cin >> T >> M;

    const int K = 5005;  // 覆盖 sum(C) <= 5000
    vector<vector<int>> C(K, vector<int>(K, 0));
    C[0][0] = 1;
    for (int n = 1; n < K; n++) {
        C[n][0] = 1;
        for (int k = 1; k <= n; k++) {
            long long v = (long long)C[n - 1][k - 1] + C[n - 1][k];
            C[n][k] = v % M;
        }
    }

    while (T--) {
        int N;
        cin >> N;
        long long ans = 1, s = 0;
        for (int i = 0; i < N; i++) {
            long long c;
            cin >> c;
            s += c;                         // s = C1 + ... + Ci
            ans = ans * C[s][c] % M;        // ans *= binom(s, c)
        }
        cout << ans << "\n";
    }
    return 0;
}

官方题解的 Python 实现：

T, mod = map(int, input().split())

K = 5010
binom = [[0] * K for i in range(K)]
binom[0][0] = 1
for n in range(1, K):
    binom[n][0] = 1
    for k in range(1, n + 1):
        binom[n][k] = (binom[n - 1][k - 1] + binom[n - 1][k]) % mod

for _ in range(T):
    N = int(input())
    C = list(map(int, input().split()))
    ans = 1
    s = 0
    for c in C:
        s += c
        ans *= binom[s][c]
        ans %= mod
    print(ans % mod)

复杂度分析

时间复杂度：预处理 $O(K^2)$ （ $K=5000$ ），每个测试用例 $O(N)$
空间复杂度： $O(K^2)$ （二项式系数表）

F - Inserting Process

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_f

题目大意

给定长度为 $N$ （ $N\le 22$ ）的小写字母串 $T$ 。统计满足以下条件的字符串序列 $s=(s_0,s_1,\ldots,s_N)$ 的个数，对 $998244353$ 取模：

$s_0$ 是空串；
对 $i=1,\ldots,N$ ， $s_i$ 是在 $s_{i-1}$ 的任意位置（含首尾）插入一个任意字符得到的；
$s_N=T$ 。

思路

反向思考：从 $T$ 删字符

把过程倒过来：从 $T$ 出发，每次删掉一个字符，最终得到空串。用一个下标集合 $S=\{S_1<S_2<\cdots<S_k\}$ 表示"当前串仍保留的字符在 $T$ 中的位置"。删除一个字符就等价于从 $S$ 中删掉一个元素。

关键问题：不同删除方式可能产生同一个字符串序列

例如 $T=\texttt{aab}$ ：先删第 1 个 a 或先删第 2 个 a，得到的下一层串都是 ab，进而产生完全相同的字符串序列（反向看都是 "" -> "a" -> "ab" -> "aab"）。因此直接数"删除方式"会重复计数。

去重规则：连续相同字符"从左往右删"

加上如下规范约束：

若 $S$ 中相邻的两个位置 $S_{i-1},S_i$ 满足 $T_{S_{i-1}}=T_{S_i}$ ，则禁止删除右边的 $S_i$ 。

也就是说，对每一段连续相同的字符，总是先删最左边的一个。

为什么这条规则恰好给出双射：

一个删除顺序的逆过程就是一个插入顺序，不同删除顺序产生相同字符串序列，当且仅当它们的差异只发生在"某段连续相同字符内部"（此时删左删右得到的字符串相同）。
规定"每段相同字符总是先删最左"，就把每一类等价删除方式挑出了唯一代表；反向理解就是"在构造 $T$ 时，一段连续相同字符中最左的那个最后插入"，这为每个字符串序列确定了一个唯一的规范化反向过程。
反之，满足该规则的任意删除顺序都对应一个合法字符串序列；不同规则删除顺序在第一次分歧处删除的字符位于不同的段（同段只允许删最左、最左是唯一的），得到的字符串必然不同。

以 $T=\texttt{aab}$ 为例：满足规则的删除顺序恰好 3 种——先删 b；先删第 1 个 a 再删第 2 个 a；先删第 1 个 a 再删 b（先删第 2 个 a 是被禁止的，因为其左侧剩余字符同为 a），对应答案 3，与样例一致。

状态压缩 DP

设 dp[mask] 表示"当前剩余字符的下标集合为 mask 时，按规范规则删空的方案数"。初始 dp[(1<<N)-1] = 1，答案 dp[0]。

转移：对 mask 中每个为 1 的位置 i，找出 mask 中它左边最近的剩余位置 pre。若 pre 不存在（i 是当前最左剩余字符）或 $T[pre]\ne T[i]$ ，则可以从 mask 删除 i，即

dp[mask \oplus (1\ll i)] \mathrel{+}= dp[mask].

注意 mask ^ (1<<i) < mask 恒成立（清除一个 1 只会让数值变小），所以从大到小枚举 mask 即可保证转移方向正确。

复杂度：状态数 $2^N\le 2^{22}\approx 4.2\times 10^6$ ，每个状态扫 $N$ 位，总复杂度 $O(N2^N)$ ，在 C++ 中很快。模数为 $998244353$ ，累加两次不超过 $2\times 10^9$ ，仍小于 int 上限，用"加后判减"即可安全取模。

参考代码

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

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

    int n;
    string t;
    cin >> n >> t;

    const int MOD = 998244353;
    vector<int> dp(1 << n, 0);
    dp[(1 << n) - 1] = 1;  // 初始剩余全部字符

    for (int mask = (1 << n) - 1; mask >= 0; mask--) {
        if (dp[mask] == 0) continue;
        char pre = 0;  // 0 不等于任何小写字母，保证最左字符可删
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                if (pre != t[i]) {  // 左边无剩余字符，或字符不同 → 允许删除
                    int &to = dp[mask ^ (1 << i)];
                    to += dp[mask];
                    if (to >= MOD) to -= MOD;
                }
                pre = t[i];  // 更新"左边最近剩余字符"
            }
        }
    }

    cout << dp[0] << '\n';
    return 0;
}

官方题解的 Python 实现：

mod = 998244353

n = int(input())
t = input()
dp = [0] * (1 << n)
dp[(1 << n) - 1] = 1
for bit in range((1 << n) - 1, -1, -1):
    dp[bit] %= mod
    pre = "?"
    for i in range(n):
        if (bit >> i) & 1:
            if pre != t[i]:
                dp[bit ^ (1 << i)] += dp[bit]
            pre = t[i]

print(dp[0])

复杂度分析

时间复杂度： $O(N\cdot 2^N)$
空间复杂度： $O(2^N)$

G - Sum of Min of XOR

题目链接：https://atcoder.jp/contests/abc425/tasks/abc425_g

题目大意

给定 $N$ 个非负整数 $A_1,\ldots,A_N$ 与正整数 $M$ ，求

\sum_{x=0}^{M-1}\min_{1\le i\le N}(x\oplus A_i),

其中 $\oplus$ 为按位异或。 $N\le 2\times 10^5$ ， $M\le 10^9$ ， $A_i\le 10^9$ 。

思路

定义递归函数

由于 $M\le 10^9<2^{30}$ 且 $A_i\le 10^9<2^{30}$ ，可以把所有数看成 $30$ 位以内的二进制。定义

f(A,M,k)=\sum_{x=0}^{M-1}\min_{a\in A}(x\oplus a),

要求 $A$ 中所有元素都小于 $2^k$ 且 $M\le 2^k$ 。我们要求的就是 $f(A,M,30)$ 。边界： $k=0$ 或 $M=0$ 时 $f=0$ （此时所有异或值都为 0）。

按最高位划分集合

设 $k\ge 1$ ， $mid=2^{k-1}$ 。把所有 $x\in[0,M)$ 按第 $k-1$ 位（最高位）分为两类： $x<mid$ （高位为 0）与 $x\ge mid$ （高位为 1，此时 $x=mid+x'$ ）。同时把 $A$ 分成两组：

$B_0=\{a\in A\mid a<mid\}$ ：最高位为 0；
$B_1=\{a-mid\mid a\in A,\ a\ge mid\}$ ：最高位为 1，减去 $mid$ 后对齐。

由于异或的每一位互不影响，有下面的基本结论（对 $x'<mid$ ）：

(x')\oplus(mid+b)=mid+(x'\oplus b),\qquad (mid+x')\oplus b=x'\oplus b.

即"异或结果的最高位由 $x$ 与 $a$ 的最高位是否相同决定"。由此可得：

对 $x<mid$ ：若 $B_0$ 非空，最小值来自 $B_0$ （数值 $<mid$ ）；若 $B_0$ 为空，最小值来自 $B_1$ ，且比 $B_1$ 内部的最小值大 $mid$ ；
对 $x=mid+x'\ge mid$ ：若 $B_1$ 非空，最小值来自 $B_1$ ；若 $B_1$ 为空，最小值来自 $B_0$ ，且加上 $mid$ 。

分情况写出递归式

情况 1： $M=2^k$ 。 $x$ 取遍 $[0,2^k)$ ，高低两半各占一半。

若 $B_0,B_1$ 均非空：高位为 0 的一半取 $B_0$ ，高位为 1 的一半取 $B_1$ ，故 $f(A,2^k,k)=f(B_0,mid,k-1)+f(B_1,mid,k-1).$
若 $B_0$ 为空：低位一半的最小值都要加 $mid$ ，共 $mid$ 个数，故 $f(A,2^k,k)=2f(B_1,mid,k-1)+mid^2.$
若 $B_1$ 为空：同理 $f(A,2^k,k)=2f(B_0,mid,k-1)+mid^2$ 。

情况 2： $M\le mid$ 。 所有 $x<M\le mid$ 最高位均为 0， $x=x'$ 。

若 $B_0$ 为空：最小值来自 $B_1$ 且整体加 $mid$ ，共 $M$ 个 $x$ ， $f(A,M,k)=f(B_1,M,k-1)+M\cdot mid.$
若 $B_0$ 非空： $B_1$ 中的元素不可能成为最小值（ $B_0$ 给出的值 $<mid$ ，而 $B_1$ 给出的值 $\ge mid$ ）， $f(A,M,k)=f(B_0,M,k-1).$

情况 3： $mid<M<2^k$ 。 把 $x$ 分成 $[0,mid)$ （共 $mid$ 个）与 $[mid,M)$ （共 $M-mid$ 个）两段分别计算后相加。

第一段（ $x<mid$ ， $x'$ 取遍 $[0,mid)$ ）： $B_0$ 为空时贡献 $f(B_1,mid,k-1)+mid^2$ ；否则贡献 $f(B_0,mid,k-1)$ 。
第二段（ $x=mid+x'$ ， $x'\in[0,M-mid)$ ）： $B_1$ 为空时贡献 $f(B_0,M-mid,k-1)+(M-mid)\cdot mid$ ；否则贡献 $f(B_1,M-mid,k-1)$ 。

为什么这样是高效的：每次调用都把集合按最高位划分成两个不交的子集，递归只落在非空的子集上（空的一侧用公式直接处理，不再把整个集合传下去）。每个递归层处理的总元素数不超过 $O(N)$ ，而二进制位数最多约 $30$ 层，总复杂度 $O(N\log(\max A))$ 。

边界与易错点：递归前保证 $A$ 非空（题目保证 $N\ge 1$ ）；答案可能达到 $M\cdot 2^{30}\approx 10^{18}$ ，必须用 64 位整数；中间量 $mid^2\le 2^{58}$ 也需 long long。

参考代码

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

// f(A, M, k) = sum_{x=0}^{M-1} min_{a in A} (x XOR a)
// 前置条件：M <= 2^k，A 中所有元素均 < 2^k
long long f(const vector<long long>& A, long long M, int k) {
    if (k == 0 || M == 0 || A.empty()) return 0;

    long long mid = 1LL << (k - 1);
    vector<long long> B0, B1;
    for (long long a : A) {
        if (a < mid) B0.push_back(a);
        else B1.push_back(a - mid);  // 减去最高位后对齐
    }

    if (M == (1LL << k)) {  // 情况 1：x 取遍 [0, 2^k)
        if (!B0.empty() && !B1.empty())
            return f(B0, mid, k - 1) + f(B1, mid, k - 1);
        if (B0.empty()) return 2 * f(B1, mid, k - 1) + mid * mid;
        return 2 * f(B0, mid, k - 1) + mid * mid;
    }

    if (M <= mid) {  // 情况 2：所有 x 的最高位均为 0
        if (B0.empty()) return f(B1, M, k - 1) + M * mid;
        return f(B0, M, k - 1);
    }

    // 情况 3：mid < M < 2^k，分两段
    long long ans = 0, rest = M - mid;
    if (B0.empty()) ans += f(B1, mid, k - 1) + mid * mid;
    else ans += f(B0, mid, k - 1);
    if (B1.empty()) ans += f(B0, rest, k - 1) + rest * mid;
    else ans += f(B1, rest, k - 1);
    return ans;
}

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

    int N;
    long long M;
    cin >> N >> M;
    vector<long long> A(N);
    long long mx = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        mx = max(mx, A[i]);
    }

    // 取最小的 k 使得 2^k > max(mx, M)，满足递归前置条件
    int k = 1;
    while ((1LL << k) <= max(mx, M)) k++;

    cout << f(A, M, k) << '\n';
    return 0;
}

官方题解的 Python 实现（其巧妙之处在于当某一半为空时直接递归整个集合 $A$ ，借助"最高位对异或值的影响可用公式补回"这一事实，与上面的写法等价）：

def f(A, M, k):
    if k == 0:
        return 0
    B = [[], []]
    for i in A:
        B[(i >> (k - 1)) & 1].append(i & ~(1 << (k - 1)))
    mid = 1 << (k - 1)
    if M == 1 << k:
        if B[0] and B[1]:
            return f(B[0], mid, k - 1) + f(B[1], mid, k - 1)
        return 2 * f(A, mid, k - 1) + mid * mid
    ans = f(B[0], min(M, mid), k - 1) if B[0] else f(A, min(M, mid), k - 1) + mid * min(M, mid)
    if M > mid:
        ans += f(B[1], M - mid, k - 1) if B[1] else f(A, M - mid, k - 1) + mid * (M - mid)
    return ans

N, M = map(int, input().split())
A = list(map(int, input().split()))
print(f(A, M, 30))

复杂度分析

时间复杂度： $O(N\log(\max A))$ （约 $30$ 层递归，每层总工作量 $O(N)$ ）
空间复杂度： $O(N)$ （每次递归的划分临时数组）