AtCoder Beginner Contest 469 题解

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

比赛概览

本场整体难度中等偏易，前四题（A–D）属于入门到普及的难度，后三题逐渐拉开差距。E 题是"二分答案 + 前缀和 + 双指针"的经典综合题；F 题考察最大生成树的 Kruskal 优化与调和级数复杂度分析；G 题则是一道结合二面体群（dihedral group）与矩阵快速幂的难题。F、G 两题都强调"把抽象变换编码为可快速计算的结构"，是本次最有区分度的题目，值得重点掌握。

---

A - Train Car

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_a

题目大意

一列火车有 $N$ 节车厢。求从车头数第 $K$ 节车厢，从车尾数起是第几节。

思路

从车头给车厢依次编号 $1,2,\dots,N$，则第 $K$ 节车厢的编号为 $K$。它后面还有编号 $K+1,K+2,\dots,N$ 共 $N-K$ 节车厢，因此从车尾数它是第 $N-K+1$ 节。

答案即 $N-K+1$。这是最直接的算术题，注意从"从前往后第 K"到"从后往前第几"的换算关系即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, K;
    cin >> N >> K;
    cout << N - K + 1 << '\n';
    return 0;
}

N, K = map(int, input().split())
print(N - K + 1)

复杂度分析

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

---

B - Isolated Seats

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_b

题目大意

有 $N$ 把椅子从左到右排成一排，给定长度为 $N$ 的字符串 $S$：第 $i$ 个字符为 o 表示第 $i$ 把椅子有人坐，为 x 表示没人坐。求满足以下全部条件的椅子数量：

• 这把椅子本身没有人坐；
• 它的左边没有椅子，或者左边的椅子没有人坐；
• 它的右边没有椅子，或者右边的椅子没有人坐。

思路

直接枚举每把椅子，检查它自身及左右两侧是否都为空即可。$N \le 100$，暴力检查完全没有问题。

为避免对最左、最右两把椅子单独写边界判断，可以使用"哨兵"技巧：在 $S$ 左右各补一个 x，得到 $T = \texttt{"x"} + S + \texttt{"x"}$。这样原来首尾的椅子在 $T$ 中也有了虚拟的空邻居，只需对中间 $N$ 个位置统一判断 $T[i-1]$、$T[i]$、$T[i+1]$ 是否全部为 x。

这个"补哨兵统一边界"的想法在更复杂的题目（如双指针、区间问题）中经常能显著减少实现量。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N; string S;
    cin >> N >> S;
    string T = "x" + S + "x";   // 左右各补一个空椅子
    int ans = 0;
    for(int i = 1; i <= N; i++){
        if(T[i-1] == 'x' && T[i] == 'x' && T[i+1] == 'x') ans++;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

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

---

C - Cantrip

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_c

题目大意

有 $N$ 个袋子排成一排，每个袋子里有一颗糖，袋子上写着 o（hit）或 x（miss）。对每个 $k=1,2,\dots,N$，高桥君先拿走队伍最前面的 $k$ 个袋子，吃掉里面的糖并保留袋子；然后只要队伍中还有袋子、且他手中还有写着 o 的袋子，就重复：丢弃一个写着 o 的袋子，拿走队伍最前面的袋子，吃掉糖并保留它。求每种 $k$ 下他能吃到的糖的总数。

思路

关键观察：高桥君手中始终恰好持有 $k$ 个袋子——每执行一次动作，丢弃一个、又拿进一个，数量不变。

他只会丢弃写着 o 的袋子，绝不会丢弃 x 袋子，因此他手中的 x 袋子数恰好等于"所有已拿到的袋子中 x 的总数"。设已拿到的袋子中有 $t$ 个 x，则手中有 $t$ 个 x 袋和 $k-t$ 个 o 袋。只要 $k-t \ge 1$（手中还有 o 可丢弃）且队伍未空，他就能继续。

所以过程停止当且仅当下面两条之一成立：

1. 他已拿到 $k$ 个 x 袋子（此时手中全是 x，无可丢弃的 o）；
2. 队伍被清空。

由此得到简洁的结论：

• 若整串 $S$ 中 x 的总数小于 $k$，则永远凑不齐 $k$ 个 x，他会一直拿到队伍空，即拿走全部 $N$ 个袋子，答案为 $N$；
• 否则，设 $p$ 为 $S$ 中第 $k$ 个 x 所在的位置，他会一直拿到并包括第 $k$ 个 x 为止，答案为 $p$。

吃掉糖的数量等于收到的袋子数量（每收到一袋必吃一颗），所以答案就是上述拿到的袋数。预处理所有 x 的位置后，每个 $k$ 的答案 $O(1)$ 可得。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; string S;
    cin >> N >> S;
    vector<int> xpos;
    for(int i = 0; i < N; i++)
        if(S[i] == 'x') xpos.push_back(i + 1);   // 1-indexed
    int total = (int)xpos.size();
    for(int k = 1; k <= N; k++){
        if(k > total) cout << N << '\n';         // x 不够 k 个，全拿完
        else          cout << xpos[k-1] << '\n'; // 拿到第 k 个 x
    }
    return 0;
}

复杂度分析

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

---

D - The Big Two

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_d

题目大意

有 $N$ 名玩家 $1,2,\dots,N$，举办了 $M$ 次比赛，第 $m$ 次进入决赛的两名玩家为 $(A_m,B_m)$。求满足 $1 \le x < y \le N$，且"每一次比赛中，$x$ 和 $y$ 至少有一人进入决赛"的二元组 $(x,y)$ 的数量。

思路

条件等价于：对每个 $m$ 都有

$$\{x,y\} \cap \{A_m,B_m\} \ne \varnothing.$$

关键观察：第一次比赛的两位决赛选手 $a=A_1$、$b=B_1$ 中，$x$ 与 $y$ 至少有一个必须等于 $a$ 或 $b$（否则第一场比赛就无法命中）。因此所有合法二元组必定含有 $a$ 或 $b$，我们只需分别统计"含 $a$ 的合法对"与"含 $b$ 的合法对"，再减去重复计数的部分。

以 $a$ 为例，考虑所有能与 $a$ 组成合法对的伙伴 $y$：

• 若 $a$ 出现在全部 $M$ 次比赛的决赛中，那么任意 $y \ne a$ 都能与 $a$ 构成合法对（因为每场比赛都靠 $a$ 命中），数量为 $N-1$；
• 否则，设 $U_a = \{m : a \notin \{A_m,B_m\}\}$ 为 $a$ 缺席的比赛集合。对这些比赛，必须依靠 $y$ 来命中，即 $y \in \{A_m,B_m\}$。故 $y$ 必须属于所有这些集合的交集

$$C_a = \bigcap_{m \in U_a} \{A_m,B_m\},$$

合法的 $y$ 数量为 $|C_a|$。

对 $b$ 完全同理得到 $C_b$。

记 $P_a$ 为"含 $a$ 的合法对"集合，$P_b$ 为"含 $b$ 的合法对"集合。答案即 $|P_a \cup P_b|$。注意到：$P_a$ 中的对必含 $a$，$P_b$ 中的对必含 $b$，因此同时属于两者的对必然同时含 $a$ 和 $b$，即只有可能是 $\{a,b\}$ 这一对。于是

$$\text{ans} = |P_a| + |P_b| - [\{a,b\}\ \text{合法}],$$

其中 $[\cdot]$ 为指示函数。判断 $\{a,b\}$ 是否合法只需检查每一场比赛是否至少包含 $a$、$b$ 之一。

实现要点：每个集合大小至多为 $2$，求交集只需线性扫描一遍比赛记录，总复杂度 $O(N+M)$。注意去重，避免 $\{a,b\}$ 被同时计入 $P_a$ 和 $P_b$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<pair<int,int>> t(M);
    vector<int> cnt(N + 1, 0);
    for(int i = 0; i < M; i++){
        int a, b; cin >> a >> b;
        t[i] = {a, b};
        cnt[a]++; cnt[b]++;
    }
    int A = t[0].first, B = t[0].second;

    // 与 x 组成合法对的伙伴数量
    auto partners = [&](int x) -> ll {
        if(cnt[x] == M) return (ll)N - 1;       // x 每场都进决赛
        vector<int> C;
        bool init = false;
        for(auto [u, v] : t){
            if(u != x && v != x){               // x 缺席的比赛
                if(!init){ C = {u, v}; init = true; }
                else{
                    vector<int> nxt;
                    for(int c : C) if(c == u || c == v) nxt.push_back(c);
                    C = nxt;
                }
            }
        }
        return (ll)C.size();
    };

    ll pa = partners(A), pb = partners(B);
    bool validAB = true;                        // {A,B} 是否合法
    for(auto [u, v] : t)
        if(u != A && u != B && v != A && v != B){ validAB = false; break; }
    cout << pa + pb - (validAB ? 1LL : 0LL) << '\n';
    return 0;
}

复杂度分析

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

---

E - Pro Exam Eligibility

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_e

题目大意

给定长度为 $N$、由 o/x 组成的字符串 $S$，表示 $N$ 场比赛的结果（o 为胜）。保证 $S$ 中 o 的个数至少为 $K$。高桥君选择区间 $[l,r]$（$1 \le l \le r \le N$），要求其中 o 的个数不少于 $K$。求在此约束下，区间内胜率（胜场数除以区间长度）的最大值。

思路

最大化一个"比值"问题，典型的做法是二分答案：二分胜率 $p$，判断是否存在"胜场 $\ge K$ 且胜率 $\ge p$"的区间。

判定条件的转化

对固定的 $p$，构造数组

$$A_i = \begin{cases} 1 - p & (S_i = \text{o}), \\ -p & (S_i = \text{x}), \end{cases}$$

则区间 $[l,r]$ 的胜率为 $\dfrac{\#\text{o}}{r-l+1}$，而

$$\sum_{i=l}^{r} A_i = \#\text{o} - p \cdot (r-l+1).$$

所以区间胜率 $\ge p$ 当且仅当 $\sum_{i=l}^{r} A_i \ge 0$。

设前缀和 $P_i = \sum_{j=1}^{i} A_j$（$P_0=0$），则该条件等价于

$$P_r - P_{l-1} \ge 0 \iff P_{l-1} \le P_r.$$

枚举右端点

对每个右端点 $r$，我们要判断是否存在合法的 $l$。由于胜场数 $\#\text{o}(l,r)$ 随 $l$ 增大而单调不增，所有满足"胜场 $\ge K$"的 $l$ 恰好构成一个前缀区间 $[1, l_r]$，其中 $l_r$ 是最大的合法左端点。

$l_r$ 可以用双指针（滑动窗口） $O(N)$ 求出：维护窗口 $[l, r]$ 内的胜场数 $w$，每加入一个新字符 $S_r$，就不断尝试右移 $l$：只要把 $S_l$ 移出窗口后胜场仍 $\ge K$，就右移。最终得到的 $l$ 即为 $l_r$（若 $w < K$ 说明不存在合法左端点，跳过该 $r$）。$l_r$ 随 $r$ 单调不降，双指针的均摊复杂度为 $O(N)$。

判断 $P_{l-1} \le P_r$

对每个有合法 $l_r$ 的 $r$，需要判断是否存在 $l \le l_r$ 使 $P_{l-1} \le P_r$，即

$$\min_{0 \le i \le l_r-1} P_i \le P_r.$$

预计算前缀最小值 $mn[i] = \min(P_0, P_1, \dots, P_i)$，即可 $O(1)$ 判断 $mn[l_r-1] \le P_r$。

二分

胜率 $\ge p$ 的存在性关于 $p$ 单调递减（$p$ 越小越容易满足），因此在 $[0,1]$ 上二分，二分约 80 轮即可把精度压到 $10^{-15}$ 以下，远超题目要求的 $10^{-6}$。

参考代码

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

    const double EPS = 1e-12;
    auto check = [&](double p) -> bool {
        // 前缀和 P 及其前缀最小值 mn
        vector<double> pref(N + 1, 0.0);
        for(int i = 1; i <= N; i++){
            double A = (S[i-1] == 'o') ? (1.0 - p) : (-p);
            pref[i] = pref[i-1] + A;
        }
        vector<double> mn(N + 1);
        mn[0] = pref[0];
        for(int i = 1; i <= N; i++) mn[i] = min(mn[i-1], pref[i]);

        // 双指针求每个 r 的最大合法左端点 l_r
        int l = 1, w = 0;
        for(int r = 1; r <= N; r++){
            if(S[r-1] == 'o') w++;
            while(l < r && w - (S[l-1] == 'o' ? 1 : 0) >= K){
                if(S[l-1] == 'o') w--;
                l++;
            }
            if(w >= K && mn[l-1] <= pref[r] + EPS) return true;
        }
        return false;
    };

    double lo = 0.0, hi = 1.0;
    for(int it = 0; it < 80; it++){
        double mid = (lo + hi) / 2;
        if(check(mid)) lo = mid;
        else           hi = mid;
    }
    cout << fixed << setprecision(15) << lo << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log C)$，其中 $C$ 是二分轮数（此处取 80，为常数）
• 空间复杂度：$O(N)$

---

F - GCD Maximum Spanning Tree

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_f

题目大意

给定长度为 $N$ 的严格递增正整数序列 $A_1 < A_2 < \dots < A_N$。在 $N$ 个点上构造带权完全无向图，点 $i$ 与点 $j$（$i<j$）之间的边权为 $\gcd(A_i,A_j)$。求该图最大生成树的边权和。

思路

朴素做法是对 $O(N^2)$ 条边跑 Kruskal，显然不可行。注意到所有边权都 $\le \max(A)$，并且 $\gcd$ 有很好的倍数结构，可以按权值级别批量处理。

维护一个并查集（DSU）。从大到小枚举 $g = \max(A), \max(A)-1, \dots, 1$，对每个 $g$：

• 枚举所有满足 $g \mid A_i$ 的下标 $i$；
• 把这些下标依次与第一个下标合并（union）。

为什么正确？ 设 $g \mid A_i$ 且 $g \mid A_j$，则 $g \mid \gcd(A_i,A_j)$，所以 $\gcd(A_i,A_j) \ge g$。

• 若 $\gcd(A_i,A_j) > g$，则这两点在处理到更大的权值级别时（即 $g' = \gcd(A_i,A_j)$ 那一轮）已经被合并进同一连通块，现在再合并是无效操作；
• 若 $\gcd(A_i,A_j) = g$，则这条边正是在权值 $g$ 级别上 Kruskal 会考虑的边，合并它恰好就是 Kruskal 的动作。

因此，按此流程执行，成功的合并次数恰好为 $N-1$，每次成功合并都对应最大生成树中的一条边，其权重就是当前的 $g$。把所有成功合并时累加的 $g$ 加起来即为答案。

复杂度：预处理 $pos[v]$ 记录值为 $v$ 的下标（$A$ 中元素互异）。对每个 $g$，枚举其不超过 $\max(A)$ 的倍数，总枚举次数为

$$\sum_{g=1}^{\max(A)} \left\lfloor \frac{\max(A)}{g} \right\rfloor = O\big(\max(A)\log \max(A)\big)$$

（调和级数）。并查集操作共 $O(N \alpha(N))$，足以通过 $N \le 2\times10^5,\ \max(A)\le10^6$。

参考代码

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b){
        a = find(a); b = find(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> A(N);
    int MAXV = 0;
    for(int i = 0; i < N; i++){ cin >> A[i]; MAXV = max(MAXV, A[i]); }

    vector<int> pos(MAXV + 1, -1);
    for(int i = 0; i < N; i++) pos[A[i]] = i;

    DSU dsu(N);
    ll ans = 0;
    for(int g = MAXV; g >= 1; g--){
        int first = -1;
        for(int m = g; m <= MAXV; m += g){
            if(pos[m] != -1){
                if(first == -1) first = pos[m];
                else if(dsu.unite(first, pos[m])) ans += g;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O\big((N + \max(A)\log\max(A))\,\alpha(N)\big)$
• 空间复杂度：$O(N + \max(A))$

---

G - K-nacci Operations

题目链接：https://atcoder.jp/contests/abc469/tasks/abc469_g

题目大意

给定 $K$ 个由 a、b 组成的字符串 $S_1, S_2, \dots, S_K$。对整数 $i > K$，定义 $S_i$ 为 $S_{i-1}, S_{i-2}, \dots, S_{i-K}$ 依序拼接而成的字符串。对字符串 $T$ 依次执行 $S_N$ 中每个字符对应的操作：

• 若该字符为 a，把 $T$ 的第一个字符移到末尾（即循环左移一位）；
• 若该字符为 b，把 $T$ 整体反转。

求执行完所有操作后的 $T$。其中 $2 \le K \le 100$，$\sum_{i=1}^K |S_i| \le 2\times10^5$，$1 \le N \le 10^{18}$，$1 \le |T| \le 2\times10^5$。

思路

$S_N$ 的长度呈 K-元斐波那契式的爆炸增长，根本不可能显式构造。但有一个关键洞察：

任意一串由 a、b 组成的操作作用到 $T$ 上，结果只可能是 $T$ 的某个循环移位，或 $T$ 的某个循环移位再反转。

这正是二面体群 $D_M$（$M = |T|$）的结构。于是我们可以把一串操作压缩成二元组 $(a,b)$：

• $(a,0)$：结果是 $T$ 循环左移 $a$ 位（$a$ 对 $M$ 取模）；
• $(a,1)$：结果是 $T$ 先循环左移 $a$ 位、再整体反转。

单串效果的快速计算

对单个字符：

• a：若当前 $b=0$，则 $a \leftarrow a+1$；若 $b=1$，则 $a \leftarrow a-1$（均模 $M$）。$b$ 不变；
• b：只把 $b$ 翻转，$a$ 不变。

因此每个基础串 $S_i$（$1 \le i \le K$）的效果 $(a_i,b_i)$ 可在 $O(|S_i|)$ 内算出。

拼接的组合规则

若依次作用字符串 $X$、$Y$（等价于字符串 $X+Y$ 的作用），组合后 $U = X \circ Y$ 满足：

$$(X_a,X_b) \circ (Y_a,Y_b) = \begin{cases} (X_a + Y_a,\ Y_b), & X_b = 0,\\[2pt] (X_a - Y_a,\ 1+Y_b \bmod 2), & X_b = 1. \end{cases}$$

由此，对 $i > K$，把 $S_i = S_{i-1}+S_{i-2}+\cdots+S_{i-K}$ 从左到右逐段组合，得到递推：

$$b_i = b_{i-1} + b_{i-2} + \cdots + b_{i-K} \pmod 2,$$

$$a_i = a_{i-1} + \sum_{j=2}^{K} (-1)^{\,b_{i-1}+b_{i-2}+\cdots+b_{i-j+1}}\, a_{i-j}.$$

（组合时 $a$ 的符号由"到目前为止已反转次数的奇偶性"决定，即前面各段 $b$ 值之和模 2。）

周期性质与矩阵加速

先看 $b$：对 $i>K$，

$$b_{i+1} - b_i = b_i - b_{i-K} \pmod 2 \Longrightarrow b_{i+1} = b_{i-K}.$$

故 $b$ 以 $P = K+1$ 为周期。而 $a$ 的递推系数只依赖 $b$，所以这些系数（$\pm1$）关于下标 $i$ 也以 $P$ 为周期。

把 $a$ 序列按每 $P$ 个一组分块，令

$$V_t = \big(a_{tP+1},\, a_{tP+2},\, \dots,\, a_{(t+1)P}\big)^{\mathsf T}.$$

由于块内任意元素 $a_{P+m}$ 的递推只用得到当前块之前已算出的值，存在一个 $P\times P$ 的常矩阵 $A$，使得

$$V_{t+1} = A\, V_t.$$

$A$ 的第 $m$ 行正是 $a_{P+m}$ 对前一块中 $P$ 个值的线性组合系数，按 $m$ 从小到大构造即可（某项落回当前块时，代入已经构造好的那一行）。

于是

$$a_N = \Big( A^{\lfloor (N-1)/P \rfloor} V_0 \Big)\big[(N-1) \bmod P\big],$$

用矩阵快速幂计算，全程对 $M$ 取模。$b_N$ 直接用周期：$b_N = b_{((N-1)\bmod P)+1}$。

最后根据 $(a_N,b_N)$ 对 $T$ 做对应变换并输出。

总复杂度 $O\big(\sum_{i=1}^K |S_i| + K^3 \log N + M\big)$。$K \le 100$ 时矩阵乘法约 $10^6$ 次运算，$\log N \le 60$，完全可行。

参考代码

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

int MOD;   // 模 M，即 |T|

vector<ll> matVec(const vector<vector<ll>>& A, const vector<ll>& v){
    int n = A.size();
    vector<ll> r(n, 0);
    for(int i = 0; i < n; i++){
        ll s = 0;
        for(int j = 0; j < n; j++) s = (s + A[i][j] * v[j]) % MOD;
        r[i] = s;
    }
    return r;
}

vector<vector<ll>> matMul(const vector<vector<ll>>& A, const vector<vector<ll>>& B){
    int n = A.size();
    vector<vector<ll>> R(n, vector<ll>(n, 0));
    for(int i = 0; i < n; i++)
        for(int k = 0; k < n; k++) if(A[i][k]){
            ll aik = A[i][k];
            for(int j = 0; j < n; j++)
                R[i][j] = (R[i][j] + aik * B[k][j]) % MOD;
        }
    return R;
}

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

    int K; cin >> K;
    vector<string> S(K);
    for(int i = 0; i < K; i++) cin >> S[i];
    ll N; cin >> N;
    string T; cin >> T;

    int M = (int)T.size();
    MOD = M;
    int P = K + 1;

    // 基础串的效果 (a_i, b_i), i = 1..K
    vector<ll> a(P + 1, 0);
    vector<int> b(P + 1, 0);
    for(int i = 1; i <= K; i++){
        ll av = 0; int bv = 0;
        for(char c : S[i-1]){
            if(c == 'a'){
                if(bv == 0) av = (av + 1) % M;
                else        av = (av - 1 + M) % M;
            } else bv ^= 1;
        }
        a[i] = av; b[i] = bv;
    }

    // 求 (a_{K+1}, b_{K+1})：S_{K+1} = S_K + S_{K-1} + ... + S_1
    {
        ll xa = a[K]; int xb = b[K];
        for(int j = K - 1; j >= 1; j--){
            if(xb == 0){
                xa = (xa + a[j]) % M;
                xb = b[j];
            } else {
                xa = (xa - a[j] % M + M) % M;
                xb = (1 + b[j]) % 2;
            }
        }
        a[P] = xa; b[P] = xb;
    }

    // 按周期 P 取 b 值
    auto getB = [&](ll x) -> int { return b[((x - 1) % P) + 1]; };

    // 构造转移矩阵 A：块 -> 下一块
    vector<vector<ll>> A(P, vector<ll>(P, 0));
    vector<vector<ll>> rows;               // 当前块内已构造好的行
    for(int m = 1; m <= P; m++){
        int n = P + m;                     // 当前块第 m 个元素的下标
        vector<ll> row(P, 0);
        for(int j = 1; j <= K; j++){
            int c = 1;
            if(j >= 2){                    // 符号由前面各段 b 之和决定
                int s = 0;
                for(int tt = 1; tt <= j - 1; tt++) s ^= getB(n - tt);
                if(s == 1) c = -1;
            }
            ll idx = n - j;                // 递推用到的位置
            if(idx >= P + 1){              // 落回当前块，用已构造的行
                int rr = (int)(idx - P - 1);
                for(int col = 0; col < P; col++){
                    row[col] = (row[col] + c * rows[rr][col]) % M;
                    if(row[col] < 0) row[col] += M;
                }
            } else {                       // 落回前一块，即单位向量
                int col = (int)(idx - 1);
                row[col] = (row[col] + c) % M;
                if(row[col] < 0) row[col] += M;
            }
        }
        rows.push_back(row);
        A[m - 1] = row;
    }

    // v0 = 第一块
    vector<ll> v(P);
    for(int i = 1; i <= P; i++) v[i - 1] = a[i];

    // v = A^t * v0
    ll t = (N - 1) / P;
    int m = (int)((N - 1) % P);
    if(t > 0){
        vector<vector<ll>> base = A;
        ll e = t;
        while(e > 0){
            if(e & 1) v = matVec(base, v);
            base = matMul(base, base);
            e >>= 1;
        }
    }

    ll aN = v[m];
    int bN = getB(N);

    // 按 (aN, bN) 变换 T
    string res;
    res.reserve(M);
    for(int i = 0; i < M; i++) res += T[(i + aN) % M];  // 左移 aN 位
    if(bN == 1) reverse(res.begin(), res.end());        // 再整体反转
    cout << res << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O\big(\sum_{i=1}^{K}|S_i| + K^3 \log N + M\big)$
• 空间复杂度：$O(K^2 + M)$