AtCoder Beginner Contest 433 题解

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

比赛概览

本场整体难度适中偏上。A 是简单的一元方程判断，B 是基础的双重遍历；C 与 F 围绕"1122 串"这一概念展开，分别考察连续子串计数与子序列计数，前者用 run-length encoding，后者需要范德蒙德恒等式的组合技巧；D 是经典的"按位数分组 + 模算术"计数，属于面向量级题的基本功；E 是一道有区分度的构造题，要求构造一个行、列最大值给定且元素互不相同的矩阵，贪心 + 充分条件判断即可；F 需要较扎实的组合恒等式推导；G 则是全场最难，用后缀自动机把字符串游戏转化为 DAG 上的博弈，再跑记忆化博弈 DP。总体来说 C/D 是分水岭，E/F/G 值得重点掌握。

---

A - Happy Birthday! 4

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_a

题目大意

给定三个正整数 $X,Y,Z$。高桥君现在 $X$ 岁，青木君现在 $Y$ 岁，两人在每年 1 月 1 日会同时增加一岁。问在未来的某个时刻（含今年，即不增加岁数也算）是否存在一个时刻，使得高桥君的年龄恰好是青木君年龄的 $Z$ 倍。存在输出 Yes，否则输出 No。

思路

关键观察：两人的年龄永远是整数，且每过一年两人同时加 1。因此设 $k$（$k\ge 0$）为经过的年数，题目就是在问：是否存在非负整数 $k$ 使得

$$X+k=Z(Y+k).$$

这是一个关于 $k$ 的一元一次方程，直接解出 $k$：

$$X+k=ZY+Zk \;\Longrightarrow\; X-YZ=(Z-1)k \;\Longrightarrow\; k=\frac{X-YZ}{Z-1}.$$

因为 $Z\ge 2$，所以 $Z-1\ge 1$，不会出现除零。$k$ 必须是非负整数，因此答案为 Yes 当且仅当同时满足：

1. $X-YZ\ge 0$（保证 $k\ge 0$）；
2. $X-YZ$ 能被 $Z-1$ 整除（保证 $k$ 是整数）。

为什么正确：$k$ 只要取满足等式的非负整数，那个时刻（$k$ 年后）两人的年龄就恰好成 $Z$ 倍关系；反之若 $k$ 是负数，说明该比值关系已经"过去"了，永远不会再出现（因为当 $k\to\infty$ 时 $\frac{X+k}{Y+k}\to 1$，若 $Z>1$ 则比值在递减方向上是单向的，错过了就不会再来）。

注意边界：题目特别强调"包括今年"，即允许 $k=0$。$k=0$ 对应 $X-YZ=0$，此时两个条件都满足，输出 Yes（如样例 3：$X=50,Y=5,Z=10$，$50-50=0$，故当前就满足）。另一个易错点是当 $X-YZ$ 为负但恰好能被 $Z-1$ 整除时（例如 $X-YZ=-2,Z-1=2$），整除性成立但 $k<0$，必须输出 No——所以 $\ge 0$ 的判断必不可少。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int X, Y, Z;
    cin >> X >> Y >> Z;
    int d = X - Y * Z;
    if (d >= 0 && d % (Z - 1) == 0) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

官方题解给出的 Python 实现：

x, y, z = map(int, input().split())
if (x - y * z) % (z - 1) == 0 and x - y * z >= 0:
    print("Yes")
else:
    print("No")

复杂度分析

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

---

B - Nearest Taller

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_b

题目大意

有 $N$ 个人从左到右排成一列，第 $i$ 个人的身高为 $A_i$。对每个 $i=1,2,\ldots,N$，问是否存在站在第 $i$ 个人左边且比他高的人，若存在，找出其中离第 $i$ 个人最近的一个人的编号；不存在则输出 $-1$。

思路

关键观察：要找的是"最近的、比 $A_i$ 高的人"，而"最近"意味着我们应该从 $i$ 左边紧邻的人开始，由近及远地逐个检查。一旦找到第一个满足 $A_j>A_i$ 的 $j$，它必然就是答案。

算法：对每个 $i$，用内层循环让 $j$ 从 $i-1$ 递减到 $1$，第一个满足 $A_j>A_i$ 的 $j$ 即为所求；若内层循环跑完都没有找到，输出 $-1$。

为什么正确：由于内层循环严格按 $j=i-1,i-2,\ldots,1$ 的顺序扫描，第一个人被找到时就是所有满足条件者中距离 $i$ 最近的，因此正确。$N\le 100$，最坏情况下每个 $i$ 都要扫描 $O(N)$ 个位置，总复杂度 $O(N^2)$，绰绰有余。

易错点：题目中身高允许相等（见样例 2），判断时必须是严格的 >；输出的是编号 $j+1$（数组下标从 0 开始）。另外"左边"不包含第 $i$ 个人自己。

若把 $N$ 放大到 $10^5$ 级别，本题也可以用单调栈在 $O(N)$ 内求解（维护一个高度严格递减的栈，每次弹出所有 $A_j\le A_i$ 的栈顶，此时栈顶即为答案），但本题数据范围不需要。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        int ans = -1;
        for (int j = i - 1; j >= 0; j--) {
            if (a[j] > a[i]) {
                ans = j + 1;
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 实现：

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    ans = -1
    for j in range(i - 1, -1, -1):
        if a[j] > a[i]:
            ans = j + 1
            break
    print(ans)

复杂度分析

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

---

C - 1122 Substring 2

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_c

题目大意

给定一个由数字组成的字符串 $S$。一个非空字符串 $T$ 被称为 1122 串，如果它同时满足：

• $|T|$ 是偶数；
• $T$ 的前 $\frac{|T|}{2}$ 个字符全部相同，后 $\frac{|T|}{2}$ 个字符也全部相同；
• $T$ 的第一个字符加 $1$ 等于 $T$ 的最后一个字符。

例如 1122、01、444555 是 1122 串，而 1222、90 不是。求 $S$ 中有多少个子串是 1122 串（从不同位置取出的相同子串要分别计数）。$|S|\le 10^6$。

思路

问题转化：设一个 1122 子串 $T=S[s..e]$，其中前半段都是数字 $d$，后半段都是数字 $d+1$。因为前后两半长度相等，分界点必然位于 $S$ 的某两个相邻位置 $i$ 与 $i+1$ 之间，即

$$s+\frac{|T|}{2}-1=i,\qquad s+\frac{|T|}{2}=i+1,$$

等价于 $s+e=2i+1$。此时 $S_i=d$、$S_{i+1}=d+1$。也就是说，每个 1122 子串都唯一对应一个满足 $S_i+1=S_{i+1}$ 的"分界"位置 $i$。

统计：固定分界 $i$（满足 $S_i+1=S_{i+1}$）。设：

• $c_1$ 为以 $S_i$ 结尾的连续相同字符段的长度（即左段长度）；
• $c_2$ 为以 $S_{i+1}$ 开头的连续相同字符段的长度（即右段长度）。

子串起点 $s$ 必须落在左段内（有 $c_1$ 种选择），终点 $e$ 必须落在右段内（有 $c_2$ 种选择），并且还要满足 $s+e=2i+1$。对于起点 $s$，唯一合法的终点是 $e=2i+1-s$；当 $s$ 遍历左段的 $c_1$ 个位置时，$e$ 恰好遍历 $[i+1,\;i+c_1]$ 这 $c_1$ 个位置，其中落在右段 $[i+1,\;i+c_2]$ 内的个数为

$$\min(c_1,c_2).$$

因此该分界对答案的贡献为 $\min(c_1,c_2)$。对每个满足 $S_i+1=S_{i+1}$ 的 $i$ 求和即可。

为什么每个子串恰好被计一次：一个 1122 子串的两半各为一段连续相同数字，前半段的最后一个字符 $S_i$ 与后半段的第一个字符 $S_{i+1}$ 紧邻且相差 1，因此分界是唯一确定的；起点落在左段、终点落在右段且满足 $s+e=2i+1$，与上述计数一一对应，不会重复也不会遗漏。

实现：对 $S$ 做 run-length encoding，得到若干段 $(digit,\ length)$。然后对相邻两段，若前段的数字加 $1$ 等于后段的数字，就把 $\min(\text{两段长度})$ 累加进答案。注意比较时用整数（或字符）：'9'+1 不再是数字，条件自动不成立，无需特判，但也可以显式跳过。

以样例 2 7788788 为例：RLE 为 $($7$,2),($8$,2),($7$,1),($8$,2)$。相邻段中 7→8 出现两次（第一处 $\min(2,2)=2$，第二处 $\min(1,2)=1$），合计 $3$，与样例一致。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<pair<char, int>> runs;               // 各段数字与其长度
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;
        runs.push_back({s[i], j - i});
        i = j;
    }
    long long ans = 0;
    for (int i = 0; i + 1 < (int)runs.size(); i++) {
        if (runs[i].first + 1 == runs[i + 1].first)     // 前段 +1 等于后段
            ans += min(runs[i].second, runs[i + 1].second);
    }
    cout << ans << '\n';
    return 0;
}

官方题解（解法一，RLE）的 Python 实现：

from itertools import groupby

s = input()
a = [(v, len(list(x))) for v, x in groupby(s)]
ans = 0
for i in range(len(a) - 1):
    if int(a[i][0]) + 1 == int(a[i + 1][0]):
        ans += min(a[i][1], a[i + 1][1])
print(ans)

复杂度分析

• 时间复杂度：$O(|S|)$（RLE 只需线性扫描，统计各段长度）
• 空间复杂度：$O(|S|)$（存储各段；若不显式存储，仅用两个辅助数组也可做到 $O(|S|)$）

---

D - 183183

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_d

题目大意

对正整数 $x,y$，定义 $f(x,y)$ 为把 $x,y$ 的十进制表示（不带前导零）依次拼接后得到的新整数，例如 $f(12,3)=123,\ f(100,40)=10040$。给定正整数 $N,M$ 和长为 $N$ 的正整数序列 $A=(A_1,\ldots,A_N)$，求满足 $1\le i,j\le N$ 且 $f(A_i,A_j)$ 是 $M$ 的倍数的有序对 $(i,j)$ 的个数。$N\le 2\times10^5,\ M\le 10^9,\ A_i\le 10^9$。

思路

问题转化：设 $A_j$ 的十进制位数为 $k$，则拼接的本质是"把 $A_j$ 放在 $A_i$ 后面"，即

$$f(A_i,A_j)=A_i\cdot 10^{k}+A_j.$$

于是 $f(A_i,A_j)$ 是 $M$ 的倍数当且仅当

$$A_i\cdot 10^k+A_j\equiv 0 \pmod M \iff A_j\equiv -A_i\cdot 10^k \pmod M.$$

算法：由于 $A_i\le 10^9$，位数最多为 $10$。把所有的 $A_j$ 按位数 $k\in\{1,\ldots,10\}$ 分组，每组存下每个 $A_j\bmod M$ 的值并排序。然后对每个 $i$、每个位数 $k$：

1. 计算 $r = -A_i\cdot 10^k \bmod M$；
2. 在第 $k$ 组中用二分查找数出值等于 $r$ 的元素个数，累加到答案。

这样，对于固定的 $(i,k)$，所有满足 $f(A_i,A_j)\equiv 0\pmod M$ 且位数为 $k$ 的 $j$ 都被精确计数；遍历全部 $k$ 后，以 $A_i$ 为前项的合法对全部统计完毕。由于外层遍历所有 $i$、内层按位数分组查找，每一对 $(i,j)$ 恰好在其 $j$ 的位数那一组被计数一次，不重不漏。注意 $i=j$ 也是允许的，该计数方式天然涵盖。

实现细节：计算 $A_i\cdot 10^k \bmod M$ 时无需快速幂，令 cur = A_i % M，然后每轮循环 cur = cur * 10 % M 即可顺序得到 $k=1,2,\ldots,10$ 对应的值；目标余数取 key = (M - cur) % M（当 cur=0 时 key=0，(M-0)%M 在 C++ 中为 0，正确）。用 lower_bound/upper_bound 即可统计区间内等于 key 的个数。$M$ 与乘积均可能超过 int，全部使用 long long 更稳妥。

为什么正确：推导中的同余等价关系是充要条件；二分查找基于已排序的分组数组，统计的是"所有位数为 $k$ 且模 $M$ 余 $key$ 的 $A_j$ 的个数"，与条件的表述完全一致。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<vector<long long>> g(11);            // g[k]: 位数为 k 的数的模值
    for (long long v : a)
        g[to_string(v).size()].push_back(v % m);
    for (auto &gg : g) sort(gg.begin(), gg.end());

    long long ans = 0;
    for (long long ai : a) {
        long long cur = ai % m;
        for (int k = 1; k <= 10; k++) {
            cur = cur * 10 % m;                 // 此时 cur = A_i * 10^k mod M
            long long key = (m - cur) % m;      // 需要的 A_j mod M
            ans += upper_bound(g[k].begin(), g[k].end(), key)
                 - lower_bound(g[k].begin(), g[k].end(), key);
        }
    }
    cout << ans << '\n';
    return 0;
}

官方题解给出的 Python 实现：

import bisect
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
g = [[] for _ in range(11)]
for v in a:
    g[len(str(v))].append(v % m)
for gg in g:
    gg.sort()
ans = 0
for ai in a:
    for k in range(1, 11):
        ai = (ai * 10) % m
        key = (m - ai) % m
        ans += bisect.bisect_left(g[k], key + 1) - bisect.bisect_left(g[k], key)
print(ans)

复杂度分析

• 时间复杂度：$O(N\cdot 10\cdot \log N)$，即 $O(N\log N)$（常数约为 $10$）
• 空间复杂度：$O(N)$

---

E - Max Matrix 2

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_e

题目大意

给定 $N,M$、长为 $N$ 的整数序列 $X=(X_1,\ldots,X_N)$ 和长为 $M$ 的序列 $Y=(Y_1,\ldots,Y_M)$。问是否存在一个 $N\times M$ 的整数矩阵 $A$，满足：

• 所有 $A_{i,j}$ 都在 $[1, NM]$ 内，且两两不同（由于共有 $NM$ 个格子、恰好 $NM$ 个可选值，等价于 $A$ 是 $1..NM$ 的一个排列）；
• 第 $i$ 行的最大值恰为 $X_i$；
• 第 $j$ 列的最大值恰为 $Y_j$。

存在则输出 Yes 与任意一个合法矩阵，否则输出 No。共 $T$ 组数据，$\sum N\times M\le 2\times 10^5$。

思路

必要条件（重复即无解）：若 $X$ 中有重复值 $v$，说明有两行的最大值都是 $v$，而 $v$ 在矩阵中只能出现一次、又必须出现在每一行内作为该行最大值，矛盾。$Y$ 同理。因此先检查 $X,Y$ 各自内部是否有重复，若有直接输出 No。

贪心构造：从大到小依次放置值 $v=NM, NM-1,\ldots,1$。定义辅助信息：

• $gx[v]$：满足 $X_i=v$ 的行号（不存在则为 $-1$）；
• $gy[v]$：满足 $Y_j=v$ 的列号（不存在则为 $-1$）；
• $ok[v]$：满足 $\min(X_i,Y_j)=v$ 的所有格子 $(i,j)$ 的集合。

一个格子 $(i,j)$ 能放下值 $w$ 的前提是 $X_i\ge w$ 且 $Y_j\ge w$，即 $w\le \min(X_i,Y_j)$。所以我们把 $\min(X_i,Y_j)=v$ 的格子理解为"在轮到 $v$ 时才开始变得可用"。

维护一个队列 $q$，存放"两边最大值都比当前值大、已经可用但还没被填"的格子。按 $v$ 从大到小处理，分四种情况：

1. $v$ 同时出现在 $X$ 和 $Y$ 中：第 $gx[v]$ 行的最大值、第 $gy[v]$ 列的最大值都必须由 $v$ 承担，唯一的办法是把 $v$ 放在交叉格 $(gx[v],gy[v])$ 上。该格子满足 $\min(X_i,Y_j)=v$，属于 $ok[v]$，此时必然尚未被使用。放好后，$ok[v]$ 中其余格子全部入队。
2. $v$ 只出现在 $X$ 中（行 $i=gx[v]$）：$v$ 必须放在第 $i$ 行。由于 $v\notin Y$，任何列的最大值都不是 $v$，所以合法放置点是第 $i$ 行中满足 $Y_j>v$ 的格子——这些格子恰好就是 $ok[v]$（因为 $X_i=v$ 且 $Y_j>v$ 时 $\min(X_i,Y_j)=v$）。若 $ok[v]$ 为空，说明第 $i$ 行没有一列的最大值大于 $v$，无处安放 $v$，无解。否则从 $ok[v]$ 中任取一个格子放 $v$，其余入队。
3. $v$ 只出现在 $Y$ 中：与情况 2 对称。
4. $v$ 在 $X,Y$ 中都没出现：$v$ 是"内部值"，可以放在任意一个两边最大值都大于 $v$ 的空格里，即从队列 $q$ 中取一个格子。若 $q$ 为空，说明所有 $X_i>v$ 且 $Y_j>v$ 的格子都已被更大的值填满，$v$ 无处可放，无解。

为什么正确：

• 每个 $ok[v]$ 中的格子在处理到 $v$ 之前不会被触碰：因为一个格子唯一属于某个 $ok[w]$（$w=\min(X_i,Y_j)$），它最早只在步骤 $w$ 被加入队列。因此情况 1、2、3 中"$v$ 必须占据的格子"在需要时一定仍然空闲。
• 从队列中取格子不会破坏后续的行/列最大值：$q$ 中的格子 $(i,j)$ 满足 $\min(X_i,Y_j)>v$，即 $X_i>v$ 且 $Y_j>v$。把较小的值 $v$ 放进去不影响 $X_i,Y_j$ 这两个更大最大值的达成；而 $X_i$（或 $Y_j$）真正需要安放时，所在的行（或列）中所有 $\min(X_i,\cdot)\ge X_i$ 的格子都属于 $ok[X_i]$，直到步骤 $X_i$ 才被使用，届时仍然空闲。由于我们按从大到小填，候选空间单调不减，贪心不会"饿死"后续的必须放置。
• 失败的充分性：某一步找不到合法格，等价于"值大于 $w$ 的个数超过了 $\#\{i:X_i>w\}\cdot\#\{j:Y_j>w\}$"这个显然必要的不等式被违反，因此无解，输出 No 正确。

实现注意：建立 $ok$ 需要 $O(NM)$ 的枚举，所有 $ok$ 中的格子总数恰为 $NM$，每个格子至多入队出队一次，因此每组的复杂度为 $O(NM)$，总复杂度 $\sum NM$，满足限制。判断重复时用大小为 $NM+1$ 的数组 $gx,gy$ 即可。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        long long nm = 1LL * N * M;
        vector<long long> X(N), Y(M);
        for (auto &v : X) cin >> v;
        for (auto &v : Y) cin >> v;

        vector<int> gx(nm + 1, -1), gy(nm + 1, -1);
        bool dup = false;
        for (int i = 0; i < N; i++) {
            if (gx[X[i]] != -1) dup = true;
            gx[X[i]] = i;
        }
        for (int j = 0; j < M; j++) {
            if (gy[Y[j]] != -1) dup = true;
            gy[Y[j]] = j;
        }
        if (dup) { cout << "No\n"; continue; }

        vector<vector<pair<int, int>>> ok(nm + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                ok[min(X[i], Y[j])].push_back({i, j});

        vector<vector<long long>> ans(N, vector<long long>(M, 0));
        deque<pair<int, int>> q;
        bool fail = false;
        for (long long v = nm; v >= 1; v--) {
            if (gx[v] == -1 && gy[v] == -1) {            // 情况 4：内部值
                if (q.empty()) { fail = true; break; }
                auto [i, j] = q.front(); q.pop_front();
                ans[i][j] = v;
                for (auto &c : ok[v]) q.push_back(c);
            } else if (gx[v] == -1 || gy[v] == -1) {     // 情况 2/3：只在一侧
                if (ok[v].empty()) { fail = true; break; }
                auto [i, j] = ok[v].back(); ok[v].pop_back();
                ans[i][j] = v;
                for (auto &c : ok[v]) q.push_back(c);
            } else {                                     // 情况 1：两侧都是最大值
                int i = gx[v], j = gy[v];
                ans[i][j] = v;
                for (auto &c : ok[v])
                    if (c.first != i || c.second != j) q.push_back(c);
            }
        }
        if (fail) { cout << "No\n"; continue; }
        cout << "Yes\n";
        for (auto &row : ans) {
            for (int j = 0; j < M; j++) {
                if (j) cout << ' ';
                cout << row[j];
            }
            cout << '\n';
        }
    }
    return 0;
}

官方题解给出的 Python 实现：

import sys
from collections import deque

input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    nm = n * m
    x = [v - 1 for v in map(int, input().split())]
    y = [v - 1 for v in map(int, input().split())]

    gx = [-1] * nm
    gy = [-1] * nm
    for i in range(n):
        if gx[x[i]] != -1:
            print("No")
            return
        gx[x[i]] = i
    for j in range(m):
        if gy[y[j]] != -1:
            print("No")
            return
        gy[y[j]] = j

    ok = [[] for _ in range(nm)]
    for i in range(n):
        for j in range(m):
            ok[min(x[i], y[j])].append((i, j))

    ans = [[-1] * m for _ in range(n)]
    q = deque()

    for v in range(nm - 1, -1, -1):
        if gx[v] == -1 and gy[v] == -1:
            if not q:
                print("No")
                return
            i, j = q.popleft()
            ans[i][j] = v + 1
            for ii, jj in ok[v]:
                q.append((ii, jj))
            continue

        if gx[v] == -1 or gy[v] == -1:
            if not ok[v]:
                print("No")
                return
            i, j = ok[v].pop()
            ans[i][j] = v + 1
            for ii, jj in ok[v]:
                q.append((ii, jj))
            continue

        i, j = gx[v], gy[v]
        ans[i][j] = v + 1
        for ii, jj in ok[v]:
            if i != ii or j != jj:
                q.append((ii, jj))

    print("Yes")
    for r in ans:
        print(*r)

for _ in range(int(input())):
    solve()

复杂度分析

• 时间复杂度：$O(NM)$ 每组数据，所有数据总和为 $O\!\left(\sum N\cdot M\right)\le 2\times 10^5$
• 空间复杂度：$O(NM)$

---

F - 1122 Subsequence 2

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_f

题目大意

与 C 题相同的 1122 串定义：非空、长度为偶数、前半段全为同一个数字 $d$、后半段全为数字 $d+1$。给定数字串 $S$（$|S|\le 10^6$），求 $S$ 中有多少个（不必连续的）子序列是 1122 串，答案对 $998244353$ 取模。从不同位置取出的相同子序列分别计数。

思路

固定"中间位置"：子序列不一定连续，我们需要一个"锚点"。注意到一个 1122 串 $T$ 的长度为 $2k$，它的第 $\frac{|T|}{2}$ 个字符（即第一半的最后一个字符）是前半段的收尾，设为 $S_i$。于是 $d=S_i$，且第二半需要 $k$ 个 $d+1$。

定义量：对位置 $i$（$S_i\le 8$）：

• $p$：$S$ 中位于 $i$ 左边、数字为 $d=S_i$ 的字符个数；
• $q$：$S$ 中位于 $i$ 右边、数字为 $d+1$ 的字符个数。

若要构成总长为 $2k$ 的 1122 子序列，第一半需要从左侧的 $p$ 个 $d$ 中选出 $k-1$ 个（加上固定的 $S_i$ 共 $k$ 个），第二半需要从右侧的 $q$ 个 $d+1$ 中选出 $k$ 个，因此固定 $i$ 的贡献为

$$\sum_{k\ge 1}\binom{p}{k-1}\binom{q}{k}.$$

化简（范德蒙德恒等式）：令 $j=k-1\ge 0$，则

$$\sum_{j\ge 0}\binom{p}{j}\binom{q}{j+1} =\sum_{j\ge 0}\binom{p}{j}\binom{q}{q-1-j} =\binom{p+q}{q-1} =\binom{p+q}{p+1}.$$

其中第二步用了 $\binom{q}{j+1}=\binom{q}{q-1-j}$ 与范德蒙德恒等式 $\sum_j \binom{p}{j}\binom{q}{m-j}=\binom{p+q}{m}$。因此固定 $i$ 的贡献简化为

$$\binom{p+q}{p+1}.$$

（也可以用生成函数看：$\sum_j\binom{p}{j}\binom{q}{j+1}$ 是 $(1+x)^p$ 与 $(1+x)^q$ 卷积的 $q-1$ 次项系数，即 $\binom{p+q}{q-1}$。）

答案：对每个满足 $S_i\le 8$ 的位置 $i$ 累加 $\binom{p+q}{p+1}$ 再取模。

为什么正确：上述对应是一一对应的——任意 1122 子序列 $T$ 的第一半最后一个字符落在某个唯一位置 $i$，于是 $T$ 由"从 $i$ 左侧选 $k-1$ 个 $d$ + 位置 $i$ + 从右侧选 $k$ 个 $d+1$"唯一决定；反过来任何这样的选择都构成一个 1122 子序列。求和后每个子序列恰被计一次。

实现：预处理阶乘与阶乘逆元到 $|S|$，就能 $O(1)$ 求组合数。先统计每个数字在 $S$ 中的总出现次数 total[d]，再从左到右扫描，用 seen[d] 记录已扫过的数字计数，则扫描到 $i$ 时 $p=seen[S_i]$、$q=total[S_i+1]-seen[S_i+1]$。组合数需要 $n<k$ 时返回 $0$（例如 $q=0$ 时 $\binom{p}{p+1}=0$，自然没有贡献）。

参考代码

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

const long long MOD = 998244353;

long long modpow(long long a, long long e) {
    long long 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);
    string s;
    cin >> s;
    int n = s.size();

    vector<long long> fact(n + 1), invf(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    invf[n] = modpow(fact[n], MOD - 2);
    for (int i = n; i >= 1; i--) invf[i - 1] = invf[i] * i % MOD;
    auto comb = [&](int nn, int kk) -> long long {
        if (nn < 0 || kk < 0 || nn < kk) return 0;
        return fact[nn] * invf[kk] % MOD * invf[nn - kk] % MOD;
    };

    vector<int> total(10, 0), seen(10, 0);
    for (char c : s) total[c - '0']++;

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d <= 8) {                       // d=9 时 d+1 不存在
            int p = seen[d];                // i 左边 d 的个数
            int q = total[d + 1] - seen[d + 1];  // i 右边 d+1 的个数
            ans = (ans + comb(p + q, p + 1)) % MOD;
        }
        seen[d]++;
    }
    cout << ans << '\n';
    return 0;
}

官方题解给出的 Python 实现：

MOD = 998244353
INF = 2_000_000 + 2025

fact = [0] * (INF + 1)
finv = [0] * (INF + 1)
fact[0] = 1
for i in range(1, INF + 1):
    fact[i] = fact[i - 1] * i % MOD
finv[INF] = pow(fact[INF], MOD - 2, MOD)
for i in range(INF, 0, -1):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fact[n] * finv[k] % MOD * finv[n - k] % MOD

s = [ord(c) - ord('0') for c in input()]
n = len(s)
d = [[0] * (n + 1) for _ in range(10)]
for i in range(n):
    for j in range(10):
        d[j][i + 1] = d[j][i]
    d[s[i]][i + 1] += 1
ans = 0
for i in range(n - 1):
    if s[i] == 9:
        continue
    p = d[s[i]][i + 1] - 1
    q = d[s[i] + 1][n] - d[s[i] + 1][i + 1]
    ans = (ans + comb(p + q, p + 1)) % MOD
print(ans)

复杂度分析

• 时间复杂度：$O(|S|)$
• 空间复杂度：$O(|S|)$

---

G - Substring Game

题目链接：https://atcoder.jp/contests/abc433/tasks/abc433_g

题目大意

给定由小写字母组成的字符串 $S$。Alice 和 Bob 玩如下游戏：准备一个空串 $T$，Alice 先手，轮流操作。每次操作，当前玩家选择一个小写字母追加到 $T$ 末尾，但要求追加后 $T$ 仍然是 $S$ 的子串。无法操作的玩家输。两人都最优时，判断 Alice 是否获胜。共 $T$ 组数据，所有 $S$ 的长度之和不超过 $4\times 10^5$。

思路

转化为图上博弈：游戏状态就是当前的 $T$，一个合法的操作相当于把 $T$ 扩展成 $T+c$，其中 $T+c$ 仍是 $S$ 的子串。这是典型的有向无环图（DAG）上的普通公平博弈：每个状态是一个节点，操作是沿着边走到后继；无后继的节点是必败态，存在一条通向必败态的边的节点是必胜态。

后缀自动机：$S$ 的子串数量可能是 $O(|S|^2)$ 的，无法全部枚举。但两个不同的子串 $u,v$ 若在后缀自动机中处于同一状态，则它们具有相同的 $endpos$ 集合，从而对任意字符 $c$，$u+c$ 是子串当且仅当 $v+c$ 是子串，且扩展后到达同一状态。因此游戏等价于在 $S$ 的后缀自动机上从初始状态（代表空串）出发走一条路径：每步沿一条字符边前进，无法继续移动者输。

后缀自动机具有如下性质：

• 状态数不超过 $2|S|-1$，边数不超过 $3|S|-4$；
• 每条转移边 $p\xrightarrow{c} q$ 都满足 $\text{len}(q)>\text{len}(p)$（实际上 $\text{len}(q)\ge\text{len}(p)+1$），因此转移图是无环的。

博弈 DP：设 win[v] 表示"轮到当前玩家、棋子位于状态 $v$ 时，当前玩家是否能获胜"。则

$$\text{win}[v]=\bigvee_{v\xrightarrow{c}q}\big(\neg\,\text{win}[q]\big),$$

即存在一条走向必败态 $q$ 的边则必胜；没有出边或所有后继都必胜则必败。由于图是 DAG，可按 $\text{len}$ 从大到小对状态排序后顺序递推（后继的 $\text{len}$ 严格更大，所以先算完）。初始棋子位于空串对应的状态 $0$，若 $\text{win}[0]$ 为真则 Alice 胜，否则 Bob 胜。

为什么正确：普通公平博弈的必胜/必败判定标准（存在一步到必败态则必胜；无路可走或所有路都到必胜态则必败）是经典结论，这里状态集与转移集与后缀自动机一一对应，故完全等价。因为 DAG 无环，先手后手不会形成循环，博弈必在有限步内结束。

实现细节：用经典的 $O(|S|)$ 增量构造后缀自动机；DP 时按 $\text{len}$ 降序排列状态。对每组数据总状态、总边数都是 $O(|S|)$，所有数据求和后仍为 $O(\sum |S|)$。若用 std::sort 排序状态，多一个 $\log$ 因子；可用计数排序按 $\text{len}$ 排序以严格达到 $O(|S|)$（本题数据规模下直接排序也完全可行）。

参考代码

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

struct SuffixAutomaton {
    struct State {
        int len, link;
        array<int, 26> next;
        State() : len(0), link(-1) { next.fill(-1); }
    };
    vector<State> st;
    int last;
    SuffixAutomaton(int n = 0) {
        st.reserve(2 * n);
        st.emplace_back();
        last = 0;
    }
    void extend(int c) {
        int cur = (int)st.size();
        st.emplace_back();
        st[cur].len = st[last].len + 1;
        int p = last;
        while (p != -1 && st[p].next[c] == -1) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = (int)st.size();
                st.emplace_back();
                st[clone].len = st[p].len + 1;
                st[clone].next = st[q].next;
                st[clone].link = st[q].link;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        string S;
        cin >> S;
        SuffixAutomaton sam((int)S.size());
        for (char c : S) sam.extend(c - 'a');

        int sz = (int)sam.st.size();
        vector<int> order(sz);
        iota(order.begin(), order.end(), 0);
        // len 严格沿着转移边增大，故按 len 降序递推
        sort(order.begin(), order.end(), [&](int a, int b) {
            return sam.st[a].len > sam.st[b].len;
        });

        vector<char> win(sz, 0);
        for (int v : order) {
            bool w = false;
            for (int c = 0; c < 26 && !w; c++) {
                int q = sam.st[v].next[c];
                if (q != -1 && !win[q]) w = true;
            }
            win[v] = w;
        }
        cout << (win[0] ? "Alice" : "Bob") << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(|S|)$ 每组数据（后缀自动机构建 + 对状态数线性扫描转移；状态排序若用计数排序为 $O(|S|)$，用 std::sort 则为 $O(|S|\log |S|)$，本题规模下均可行）；全部数据为 $O\!\left(\sum |S|\right)$
• 空间复杂度：$O(|S|)$（状态数 $\le 2|S|-1$，边数 $\le 3|S|-4$）

---