AtCoder Beginner Contest 428 题解

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

AtCoder Beginner Contest 428 题解

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

比赛概览

本场整体难度偏常规：A、B 为简单签到；C 是经典括号序列的栈判定，属于必会套路；D 是按十进制位数分组、再数平方数的数论计数；E 是树的直径经典应用，难点在于编号取最大的 tie-break 处理；F 利用区间嵌套的不变式构造"块"结构，关键在摊还分析，较有区分度；G 是 Pólya 计数定理 + 卷积 DP 的难题，解法非常优雅。总体梯度平滑，值得重点掌握 C、E、F 的套路，以及 G 的 Pólya 枚举方法。

A - Grandma's Footsteps

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_a

题目大意

铃响后，高桥重复做两件事：先以每秒 $S$ 米的速度跑 $A$ 秒，再静止 $B$ 秒。问从铃响开始到 $X$ 秒结束，他一共跑了多少米。输入一行 $S\ A\ B\ X$ ，输出总距离（不含单位）。

思路

关键观察：他跑的速度恒定，因此先求出在 $X$ 秒内他一共"跑"了多少秒，再乘以 $S$ 即可。

他的动作是一个以 $A+B$ 秒为周期的循环：每个周期中前 $A$ 秒在跑、后 $B$ 秒静止。把 $X$ 秒分解为商和余数：

X = (A+B)\cdot q + r,\qquad q=\left\lfloor\frac{X}{A+B}\right\rfloor,\quad r=X \bmod (A+B).

完整周期部分：共 $q$ 个周期，每个周期跑 $A$ 秒，共 $Aq$ 秒；
余数部分 $r$ 秒：若 $r \le A$ 则全程在跑，贡献 $r$ 秒；若 $r > A$ 则只跑了前 $A$ 秒，贡献 $A$ 秒。即 $\min(r, A)$ 秒。

所以跑步总时长为

\text{len} = A\cdot\left\lfloor\frac{X}{A+B}\right\rfloor + \min\left(X \bmod (A+B),\ A\right),

答案就是 $\text{len} \times S$ 。

易错点：余数部分取 $\min(r,A)$ 而非直接取 $r$ ；另外所有数不超过 $1000$ ，用 int 即可，但写成 long long 更稳妥。

（官方题解还给出了逐秒模拟的做法，当 $X$ 很大时不可行，这里直接采用算术解法。）

参考代码

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

int main() {
    int S, A, B, X;
    cin >> S >> A >> B >> X;
    long long run = 1LL * (X / (A + B)) * A + min(X % (A + B), A);
    cout << run * S << '\n';
    return 0;
}

复杂度分析

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

B - Most Frequent Substrings

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_b

题目大意

给定长度为 $N$ 的小写字符串 $S$ 和整数 $K$ 。定义一个长度为 $K$ 的串 $t$ 的出现次数为它在 $S$ 中作为连续子串出现的次数。求 $K$ 长子串的最大出现次数 $x$ ，并输出所有出现次数恰好为 $x$ 的 $K$ 长子串（按字典序升序，空格分隔）。

思路

关键观察： $N \le 100$ ， $K$ 长子串一共只有 $N-K+1 \le 100$ 个位置，数量很小，直接枚举即可。

用关联数组（C++ 的 std::map）对每个长度为 $K$ 的子串计数：

对 $i=0,1,\dots,N-K$ ，取出 S.substr(i, K)，把 memo[t] 加 $1$ 。
遍历 memo 找到最大计数 vmax。
再遍历 memo，把所有 memo[t] == vmax 的键输出。

为什么正确：memo[t] 存的就是 $t$ 的出现次数，最大值 $x$ 与所有达到最大值的串都被完整枚举。由于 std::map 按键的字典序（std::string 默认按字典序比较）内部有序，for 遍历自然就是字典序升序，无需额外排序。

易错点：输出两行——第一行最大值，第二行是空格分隔的所有串（末尾也要换行）；第二行不能输出多余空格（用 first 标记控制）。

参考代码

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

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;

    map<string, int> memo;
    for (int i = 0; i + K <= N; i++) {
        memo[S.substr(i, K)]++;
    }

    int vmax = 0;
    for (auto &[key, val] : memo) vmax = max(vmax, val);

    cout << vmax << '\n';
    bool first = true;
    for (auto &[key, val] : memo) {
        if (val == vmax) {
            if (!first) cout << ' ';
            cout << key;
            first = false;
        }
    }
    cout << '\n';
    return 0;
}

复杂度分析

时间复杂度：枚举子串 $O((N-K+1)\cdot K)$ ，std::map 每次操作 $O(\log M)$ ，其中 $M \le N-K+1$ 为不同子串个数；总体 $O((N-K+1)\cdot K + M\log M)$ ，由于 $N \le 100$ ，可视为 $O(N^2 \log N)$ 。
空间复杂度： $O(M \cdot K) \le O(N^2)$ 。

C - Brackets Stack Query

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_c

题目大意

初始 $S$ 为空串。依次处理 $Q$ 个操作，每个操作后判断 $S$ 是否为"好括号序列"（可以由空串反复删除连续的 () 得到）：

1 c：把字符 c（( 或 )）追加到 $S$ 末尾；
2：删除 $S$ 的最后一个字符（保证此时 $S$ 非空）。

每个操作后输出 Yes/No。

思路

问题转化：好括号序列等价于"合法括号序列"，它有如下经典的判定方式。

令 $A_0=0$ ，且对 $1 \le i \le |S|$ ：

A_i = A_{i-1} + \begin{cases} +1, & S_i = \text{`(`}\\ -1, & S_i = \text{`)`}\end{cases}

即 $A_i$ 是前 $i$ 个字符的"左括号数减右括号数"（前缀和）。则 $S$ 是合法括号序列当且仅当：

A_{|S|} = 0 \quad\text{且}\quad \min_{0 \le i \le |S|} A_i = 0.

直观理解：前缀和始终非负，保证任意前缀中左括号不少于右括号（否则会出现 ) 多出来的非法前缀）；总前缀和为 $0$ ，保证左右括号数量相等。这两个条件合起来正是括号匹配的充要条件。

数据结构：由于操作只有"末尾追加"和"删除末尾"，可以用两个栈（实现上用 std::vector）分别维护：

$A$ 栈：存 $A_0, A_1, \dots, A_{|S|}$ ；
$B$ 栈：存 $B_i = \min\{A_0,\dots,A_i\}$ ，即前缀最小值。

初始两个栈各含 $0$ 。追加字符 c 时（新长度 $n=|S|$ ）：

A_n = A_{n-1} \pm 1,\qquad B_n = \min(B_{n-1},\, A_n);

删除末尾时直接对两个栈 pop_back()。每次操作后，判断 A.back() == 0 && B.back() == 0 即得答案。

为什么正确：栈中始终恰好保存当前串完整的前缀信息，追加/删除各只改动栈顶一项， $O(1)$ 维护；判定条件即上面的充要条件。 $Q \le 8\times 10^5$ ， $O(Q)$ 完全足够。

易错点：判定的是 $\min A_i = 0$ 而非 $\min A_i \ge 0$ 与 $A_n=0$ 分开看，二者必须同时满足（例如 )( 满足 $A_n=0$ 但不满足 $\min A_i = 0$ ，不是合法括号序列）。

参考代码

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

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

    int Q;
    cin >> Q;
    vector<int> A(1, 0), B(1, 0);   // 前缀和 A、前缀最小值 B

    while (Q--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            char c;
            cin >> c;
            int nv = A.back() + (c == '(' ? 1 : -1);
            A.push_back(nv);
            B.push_back(min(B.back(), nv));
        } else {
            A.pop_back();
            B.pop_back();
        }
        cout << (A.back() == 0 && B.back() == 0 ? "Yes" : "No") << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(Q)$
空间复杂度： $O(Q)$ （栈深度最大为 $|S| \le Q$ ）

D - 183184

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_d

题目大意

对正整数 $x,y$ ， $f(x,y)$ 表示把 $x$ 和 $y$ 的十进制字符串直接拼接后得到的整数（如 $f(3,14)=314$ ）。给定 $T$ 组 $(C,D)$ ，对每组求满足 $1 \le x \le D$ 且 $f(C,C+x)$ 是完全平方数的整数 $x$ 的个数。

思路

关键转化：令 $y = C + x$ ，并设 $y$ 有 $d$ 位十进制数。拼接就是" $C$ 后面跟 $y$ "，因此

f(C,C+x) = C\times 10^{d} + y = C\times 10^d + C + x.

这样就把"拼接"化成了乘法与加法，问题变为对某个 $d$ 数区间内的平方数。

按位数分组： $y$ 有 $d$ 位当且仅当 $10^{d-1} \le y \le 10^d - 1$ ，即 $x = y - C$ 满足

10^{d-1} - C \le x \le 10^d - 1 - C.

再结合 $1 \le x \le D$ ，定义

L = \max(1,\ 10^{d-1} - C),\qquad R = \min(D,\ 10^d - 1 - C).

若 $L > R$ ，该 $d$ 没有合法的 $x$ ；否则 $x \in [L, R]$ 。

计数：此时问题等价于统计区间

\big[\, C\times 10^d + C + L,\ \ C\times 10^d + C + R \,\big]

内完全平方数的个数。不超过 $k$ 的完全平方数恰好有 $\lfloor \sqrt{k} \rfloor$ 个，因此该区间的平方数个数为

\left\lfloor \sqrt{C\times 10^d + C + R} \right\rfloor - \left\lfloor \sqrt{C\times 10^d + C + L - 1} \right\rfloor.

遍历所有 $d$ ： $y \le C+D$ ，所以 $d$ 从 $1$ 取到 $C+D$ 的十进制位数即可（ $10^{d-1} > C+D$ 时无 $d$ 位数）。

数值与精度： $C \le 2\times 10^8,\ D \le 5\times 10^9$ ， $C+D \le 5.2\times 10^9$ （最多 10 位），最大被开方数约为 $2\times 10^8 \times 10^{10} = 2\times 10^{18}$ ，仍在 long long 范围内。浮点开方对 $10^{18}$ 级别的数可能产生 ±1 的误差，因此求 $\lfloor\sqrt{k}\rfloor$ 后要作校正：while (r*r > x) r--; while ((r+1)*(r+1) <= x) r++;（ $r\approx 1.4\times 10^9$ ， $r^2$ 不溢出）。

易错点： $L$ 可能为负，务必与 $1$ 取 max；每个测试独立计算；开方后要校正。

参考代码

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

typedef long long ll;

// floor(sqrt(x))，带 ±1 校正
ll isqrt(ll x) {
    ll r = (ll)sqrtl((long double)x);
    while (r > 0 && r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r;
}

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

    int T;
    cin >> T;
    while (T--) {
        ll C, D;
        cin >> C >> D;

        ll ans = 0;
        // d10 = 10^{d-1}, p = 10^d
        for (ll d10 = 1, p = 10; d10 <= C + D; d10 = p, p *= 10) {
            ll L = max(1LL, d10 - C);
            ll R = min(D, p - 1 - C);
            if (L <= R) {
                ll lo = C * p + C + L;
                ll hi = C * p + C + R;
                ans += isqrt(hi) - isqrt(lo - 1);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：每组测试 $O(\log_{10}(C+D))$ （位数数量级，最多约 10），总 $O(T \log(C+D))$ 。
空间复杂度： $O(1)$ 。

E - Farthest Vertex

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_e

题目大意

给定一棵 $N$ 个顶点的树。对每个顶点 $v$ ，输出与 $v$ 距离最远的顶点编号；若有多个顶点距离都最远，输出其中编号最大者。距离定义为路径上边的条数。

思路

关键观察 1（直径性质）：设 $(s,t)$ 是树的直径（任意一对相距最远的顶点）的两个端点。则对任意顶点 $u$ ，与 $u$ 距离最远的顶点一定是 $s$ 或 $t$ 之一，即

\max_{v} d(u,v) = \max\{d(u,s),\ d(u,t)\}.

证明（反证）：若存在某个 $v$ 同时比 $s$ 、 $t$ 离 $u$ 更远，分析 $s$ - $t$ 路径与 $u$ - $v$ 路径的位置关系（考虑两路径分离/相交的情况），可推出 $s$ - $t$ 距离比直径还长，矛盾。因此"最远距离"完全由直径端点决定。

关键观察 2（编号 tie-break）：本题要求"多个最远顶点时取编号最大者"，而直径性质只保证了"距离"层面最远点在 $\{s,t\}$ 中，并没有直接处理编号。官方题解用一个巧妙的"扩展图"来吸收编号：

给每个顶点 $i$ 新增一个复制顶点 $i'$ ，连一条长度为 $i\times 10^{-100}$ （比任何距离差都小的极小正数）的边 $i$ - $i'$ 。

在新图中，顶点 $u$ 到 $i'$ 的距离为 $d(u,i) + i\times 10^{-100}$ 。由于附加项极小，距离的比较等价于先比较 $d(u,i)$ ，相等时再比较编号 $i$ 。扩展后最远顶点唯一，且根据直径性质，这个唯一最远点必为扩展图直径的端点。因此答案是

\operatorname{arg\,max}_{i\in\{s,t\}}\left(d(u,i),\ i\right)

即对两个直径端点 $s,t$ ，取二元组 $(d(u,s),s)$ 与 $(d(u,t),t)$ 中字典序较大者对应的端点。这也等价于：距离不相等时取距离大的端点；距离相等时取编号大的端点。

算法步骤：

从任意顶点（如 $1$ 号）BFS/DFS 求距离，取距离最远的顶点为 $u$ （若有多个取编号最大者）；
从 $u$ BFS/DFS，取距离最远的顶点为 $v$ （同样编号最大者）—— $(u,v)$ 即直径端点对；
从 $v$ BFS/DFS 得到所有点到 $v$ 的距离；
对每个顶点 $i$ ，比较 $(du[i],u)$ 与 $(dv[i],v)$ 的字典序，输出较大者的编号。

为什么编号最大的取法正确：第 1、2 步中"取编号最大者"保证了 $u,v$ 恰好是扩展图直径的端点（等价于在原始的直径端点对中取编号和最大的一对），这正是把编号 tie-break 吸收进距离比较所必需的。

易错点： $N$ 可达 $5\times 10^5$ ，递归 DFS 可能爆栈，应使用 BFS 或显式栈的迭代 DFS；比较二元组时注意距离相等要取大编号。

参考代码

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

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

    int N;
    cin >> N;
    vector<vector<int>> g(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    auto bfs = [&](int s) {
        vector<int> dist(N, -1);
        queue<int> q;
        dist[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : g[u]) {
                if (dist[v] != -1) continue;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
        return dist;
    };

    auto d0 = bfs(0);
    int u = 0;
    for (int i = 1; i < N; i++)
        if (d0[i] >= d0[u]) u = i;   // 距离最大，且编号最大

    auto du = bfs(u);
    int v = 0;
    for (int i = 1; i < N; i++)
        if (du[i] >= du[v]) v = i;

    auto dv = bfs(v);

    for (int i = 0; i < N; i++) {
        int ans;
        if (du[i] > dv[i]) ans = u;
        else if (du[i] < dv[i]) ans = v;
        else ans = max(u, v);        // 距离相等取大编号
        cout << ans + 1 << '\n';
    }
    return 0;
}

官方题解给出的 Python 版本（以下为改为迭代 DFS 的写法，避免标准 Python 递归深度限制）：

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    g = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    def bfs_dist(s):
        dist = [-1] * N
        dist[s] = 0
        stack = [s]
        while stack:
            c = stack.pop()
            for d in g[c]:
                if dist[d] == -1:
                    dist[d] = dist[c] + 1
                    stack.append(d)
        return dist

    d0 = bfs_dist(0)
    u = max(range(N), key=lambda i: (d0[i], i))
    du = bfs_dist(u)
    v = max(range(N), key=lambda i: (du[i], i))
    dv = bfs_dist(v)

    for i in range(N):
        print(max((du[i], u), (dv[i], v))[1] + 1)

if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：三次遍历 $O(N)$ 。
空间复杂度： $O(N)$ 。

F - Pyramid Alignment

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_f

题目大意

数轴上有 $N$ 个区间，区间 $i$ 初始为 $[0, W_i]$ ，且 $W_1 < W_2 < \dots < W_N$ 。依次处理 $Q$ 个操作：

1 v：设 $l$ 为区间 $v$ 当前的左端点，把编号 $\le v$ 的所有区间平移使它们的左端点在 $l$ ；
2 v：设 $r$ 为区间 $v$ 当前的右端点，把编号 $\le v$ 的所有区间平移使它们的右端点在 $r$ ；
3 x：输出当前包含坐标 $x+\tfrac12$ 的区间个数。

思路

关键观察 1（嵌套不变式）：任意时刻区间始终是嵌套的：

[\,l_1,r_1] \subseteq [\,l_2,r_2] \subseteq \cdots \subseteq [\,l_N,r_N],

且每个区间的宽度保持为 $r_i - l_i = W_i$ 。初始显然成立。对操作 1：编号 $\le v$ 的区间左端统一设为 $l_v$ ，宽度不变，故它们在编号方向上仍嵌套；而新区间 $v$ 等于旧区间 $v$ （因为 $[l_v, l_v+W_v]$ 就是旧 $[l_v, r_v]$ ），区间 $v+1$ 原本就包含旧区间 $v$ ，因此跨边界也嵌套。操作 2 同理（用右端点对齐，左端点随宽度自动确定）。这个不变式是整个题目的基石。

关键观察 2（块结构）：编号相邻的区间常常"共享同一端点"。把连续编号、且左端点相同（或右端点相同）的区间合并成一个块，用四元组 $(L, R, g, x)$ 表示"编号 $L..R$ 的区间满足： $g=-1$ 时左端点都为 $x$ ， $g=+1$ 时右端点都为 $x$ "。由宽度不变式，块内区间 $i$ 的坐标完全确定：

g=-1:\ [x,\ x+W_i],\qquad g=+1:\ [x-W_i,\ x].

初始只有一个块 $(1,N,-1,0)$ （所有左端点为 $0$ ）。用栈（std::vector 当栈用，栈顶存最小编号所在块）维护块的序列。

操作 1/2：以操作 1 为例（操作 2 完全对称）。从栈顶开始弹出块，直到弹出包含编号 $v$ 的块（满足 $b.r \ge v$ ）：

若 $v < b.r$ ，把剩余部分 $(v+1, b.r, b.g, b.x)$ 压回栈；
由被弹块的性质算出区间 $v$ 当前的左（右）端点，设为 $X$ ；
把新区块 $(1, v, -1, X)$ （或操作 2 的 $(1,v,+1,X)$ ）压栈。

被弹出的所有块编号都 $\le v$ ，被新区块完整覆盖，直接丢弃即可。

为什么总复杂度是 $O(Q)$ （摊还）：设块数为 $m$ 。初始 $m=1$ ；每次操作 1/2 中，除最后一次循环外，每次弹出一个块使 $m$ 减 $1$ ，最后压入至多 2 个新块使 $m$ 最多加 $1$ 。 $Q$ 次操作后块数增量至多为 $Q+1$ ，而块数非负，故所有操作的总弹出次数 $O(Q)$ 。因此操作 1/2 摊还 $O(1)$ 。

操作 3（二分）：由于区间嵌套，包含点 $x+\tfrac12$ 的区间构成一个后缀：存在 $k$ 使得区间 $1..k$ 不包含它、区间 $k+1..N$ 都包含它，答案即 $N-k$ 。又因为所有端点都是整数，区间 $[l,r]$ 包含 $x+\tfrac12$ 当且仅当 $l \le x < r$ 。

二分分两层：先在块之间二分找到"最小右端点包含该点"的块（利用该块右端区间是否包含点作为单调谓词），再在该块内部二分找到最小编号。每层 $O(\log N)$ 。

易错点：块在栈中的顺序是"编号从大到小"还是"从小到大"要在代码里保持一致；判断包含用 $l \le x < r$ （因为 $x+\tfrac12$ 落在整数格中间）；操作 1/2 中新区块的端点要由被弹块的性质推算，不能假设区间 $v$ 在块内的左右端点形式。

参考代码

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

typedef long long ll;

struct Block {
    int li, ri;   // 编号范围（0-indexed）
    int g;        // -1: 左端点都等于 x；+1: 右端点都等于 x
    ll x;
};

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

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

    vector<Block> st;                       // 栈顶 = 最小编号所在块
    st.push_back({0, N - 1, -1, 0});

    int Q;
    cin >> Q;
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1 || type == 2) {
            int v;
            cin >> v;
            --v;
            int dir = (type == 1) ? -1 : +1;   // 对齐左端点 / 右端点

            while (true) {
                Block b = st.back();
                st.pop_back();
                if (b.ri >= v) {               // 找到包含 v 的块
                    if (v + 1 <= b.ri) {
                        st.push_back({v + 1, b.ri, b.g, b.x});
                    }
                    ll fl, fr;                 // 区间 v 的左右端点
                    if (b.g < 0) {
                        fl = b.x;
                        fr = fl + w[v];
                    } else {
                        fr = b.x;
                        fl = fr - w[v];
                    }
                    ll cx = (dir < 0) ? fl : fr;
                    st.push_back({0, v, dir, cx});
                    break;
                }
            }
        } else {
            ll x;
            cin >> x;

            // 块间二分：找最大的块下标 ok，使该块最右区间包含 x+1/2
            int ok = -1, ng = (int)st.size();
            while (ok + 1 < ng) {
                int mid = (ok + ng) / 2;
                Block &b = st[mid];
                ll fl, fr;
                if (b.g < 0) {
                    fl = b.x;
                    fr = fl + w[b.ri];
                } else {
                    fr = b.x;
                    fl = fr - w[b.ri];
                }
                if (fl <= x && x < fr) ok = mid;
                else ng = mid;
            }

            int ans;
            if (ok < 0) {                     // 没有任何区间包含该点
                ans = 0;
            } else {
                Block &b = st[ok];
                // 块内二分：找最小编号 lo2 满足区间包含该点
                int lo2 = b.ri, hi2 = b.li - 1;
                while (hi2 + 1 < lo2) {
                    int mid = (lo2 + hi2) / 2;
                    ll fl, fr;
                    if (b.g < 0) {
                        fl = b.x;
                        fr = fl + w[mid];
                    } else {
                        fr = b.x;
                        fl = fr - w[mid];
                    }
                    if (fl <= x && x < fr) lo2 = mid;
                    else hi2 = mid;
                }
                ans = N - lo2;                // 后缀长度
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

复杂度分析

时间复杂度：操作 1/2 摊还 $O(1)$ （总弹出次数 $O(Q)$ ），操作 3 为 $O(\log N)$ ；总 $O(N + Q\log N)$ 。
空间复杂度：块数 $O(Q)$ 。

G - Necklace

题目链接：https://atcoder.jp/contests/abc428/tasks/abc428_g

题目大意

有 $N$ 种宝石，每种无限供应；宝石 $i$ 的美值为 $b_i \in [2, U]$ ，同种宝石不可区分。把若干宝石围成一圈形成项链，两条项链旋转后相同视为同一条（不可翻转）。对每个 $x \in [2, U]$ ，求美值乘积恰好为 $x$ 的项链数，对 $998244353$ 取模。

思路

关键观察 1（长度上限）：每颗宝石美值 $\ge 2$ ，因此长度为 $L$ 的项链美值乘积 $\ge 2^L$ 。要满足乘积 $\le U$ ，必须

L \le V := \lfloor \log_2 U \rfloor \le \lfloor \log_2(5\times 10^5) \rfloor = 18.

所以项链长度至多 18，非常小。

第一步：先数"序列"（线性排列）。令 $A(k,n)$ 为长度 $k$ 、美值乘积为 $n$ 的宝石序列数， $f_t$ 为美值等于 $t$ 的宝石种类数。则有转移

A(0,1)=1,\qquad A(k+1,\, s\cdot t) \mathrel{+}= A(k,s)\cdot f_t.

即"在乘积为 $s$ 的序列后追加一颗美值 $t$ 的宝石"。递推到 $k=V$ 即可。复杂度 $\sum_{k,s} \lfloor U/s\rfloor = O(V\cdot U \log U) = O(U\log^2 U)$ 。

第二步：Pólya 枚举定理数项链。项链把长度 $L$ 的序列按旋转 $L$ 个方向合并等价类。由 Burnside 引理（Pólya 的直接推论），长度 $L$ 的项链数是旋转固定点数的平均：

\frac{1}{L}\sum_{i=0}^{L-1} (\text{被旋转 } i \text{ 固定的配置数}).

旋转 $i$ 把 $L$ 个位置分成 $d=\gcd(i,L)$ 个循环，每个循环长 $L/d$ 。被它固定的配置在每个循环内宝石都相同，因此由长度 $d$ 的一个序列唯一决定；若该序列的循环内乘积为 $p$ ，则总乘积为 $p^{\,L/d}$ 。令 $p^{\,L/d}=x$ ，即 $p=\sqrt[L/d]{x}$ ，固定配置数就是 $A(d,\ \sqrt[L/d]{x})$ （当 $x$ 不是 $L/d$ 次完全幂时取 $0$ ）。

把 $i$ 按 $\gcd(i,L)$ 分组： $\gcd(i,L)=L/d$ 的 $i$ 有 $\varphi(d)$ 个，于是长度 $L$ 、乘积 $x$ 的项链数为

f_L(x)=\frac{1}{L}\sum_{d\mid L}\varphi(d)\cdot A\!\left(\frac{L}{d},\ \sqrt[d]{x}\right),

其中 $\sqrt[d]{x}$ 不是整数时该项贡献为 $0$ 。总答案

f(x)=\sum_{L=1}^{V} f_L(x).

实现方式：不要对每个 $x$ 单独算，而是枚举 $(L,d)$ 后枚举 $y=\sqrt[d]{x}$ ：对每个 $d\mid L$ 、每个 $y$ 满足 $y^d\le U$ ，把 $\dfrac{\varphi(d)}{L}\cdot A(L/d,\ y)$ 加到 $f(y^d)$ 上。 $\varphi(1..V)$ 用线性筛/简单筛预计算， $L^{-1} \bmod 998244353$ 用费马小定理。这部分的复杂度是

\sum_{L=1}^{V}\sum_{d\mid L} U^{1/d} = O\!\left(V\cdot U + \sum_{d=2}^{V}\frac{V}{d}\cdot U^{1/d}\right) = O(U\log U),

主要由 $d=1$ 的 $V\cdot U \approx 9\times 10^6$ 次加法主导，非常快。

正确性补充：不同长度 $L$ 的项链是不同对象（珠子数不同），不会重复计数；Pólya 公式已处理旋转等价，且题目明确禁止翻转，所以不除以 2。

另一解法（官方进阶做法）：把宝石序列的 Dirichlet 生成函数（DGF） $A(s)=\sum_n \frac{f_n}{n^s}$ 引入，利用 Pólya 得到项链 DGF 为 $\sum_d \frac{\varphi(d)}{d}\log\frac{1}{1-A(ds)}$ ，再借助 DGF 上的"魔法导数"（以 $\Omega(n)$ 替换 $\ln n$ ）做到 $O(U\log U)$ 。该技巧很漂亮但实现复杂，本文参考代码采用上面直观的 Pólya + DP 解法。

参考代码

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

typedef long long ll;

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 N, U;
    cin >> N >> U;

    vector<int> freq(U + 1, 0);
    vector<int> vals;                       // 出现过的美值（需升序，供 DP 内层提前 break）
    for (int i = 0; i < N; i++) {
        int b;
        cin >> b;
        if (freq[b]++ == 0) vals.push_back(b);
    }
    sort(vals.begin(), vals.end());

    int V = 0;                              // V = floor(log2 U)
    while ((1LL << (V + 1)) <= U) V++;

    // A[k][n]：长度 k、乘积 n 的序列数
    vector<vector<ll>> A(V + 1, vector<ll>(U + 1, 0));
    A[0][1] = 1;
    for (int k = 0; k < V; k++) {
        for (int s = 1; s <= U; s++) {
            ll av = A[k][s];
            if (av == 0) continue;
            for (int t : vals) {
                if ((ll)s * t > U) break;
                A[k + 1][s * t] = (A[k + 1][s * t] + av * freq[t]) % MOD;
            }
        }
    }

    // 欧拉函数 phi[1..V]
    vector<int> phi(V + 1);
    for (int i = 0; i <= V; i++) phi[i] = i;
    for (int i = 2; i <= V; i++) {
        if (phi[i] == i) {                  // i 为素数
            for (int j = i; j <= V; j += i) phi[j] -= phi[j] / i;
        }
    }

    // 模逆 inv[1..V]
    vector<ll> inv(V + 1, 1);
    for (int i = 1; i <= V; i++) inv[i] = modpow(i, MOD - 2);

    vector<ll> f(U + 1, 0);
    for (int L = 1; L <= V; L++) {
        for (int d = 1; d <= L; d++) {
            if (L % d) continue;
            int k = L / d;
            ll coeff = phi[d] * inv[L] % MOD;
            ll y = 1;
            while (true) {                  // 枚举 y = x^(1/d)，满足 y^d <= U
                ll p = 1;
                for (int e = 0; e < d; e++) {
                    if (p > U / y) { p = U + 1; break; }
                    p *= y;
                }
                if (p > U) break;
                if (A[k][y] != 0) {
                    f[p] = (f[p] + coeff * A[k][y]) % MOD;
                }
                y++;
            }
        }
    }

    for (int x = 2; x <= U; x++) {
        if (x > 2) cout << ' ';
        cout << f[x];
    }
    cout << '\n';
    return 0;
}

复杂度分析

时间复杂度：序列 DP 为 $O\left(V\sum_{s=1}^{U}\lfloor U/s\rfloor\right)=O(U\log^2 U)$ ；项链求和为 $O\left(VU + \sum_{d=2}^{V}\frac{V}{d}U^{1/d}\right)=O(U\log U)$ ；总 $O(U\log^2 U)$ 。
空间复杂度： $O(V\cdot U)=O(U\log U)$ 。