AtCoder Beginner Contest 456 题解

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

AtCoder Beginner Contest 456 题解

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

比赛概览

本场 A、B 以"掷骰子"为背景，是典型的入门热身题；C、D 则是同一主题（"相邻字符不相等"）的计数题，分别考察字符串分段分析（C）与序列 DP（D），难度适中。E、F、G 围绕"假日安排"主题逐层深入：E 需要把"无限时间旅程"建模成带星期维度的有向图并判环，关键观察是环长必为 $W$ 的倍数；F 需要把 DP 转移抽象成 min-plus 矩阵并借助分块/线段树加速滑动窗口，是本场区分度最高、最值得掌握的题；G 则是容斥原理与调和级数复杂度分析的计数题。建议重点掌握 F 的 min-plus 矩阵乘技巧与 G 的容斥拆分思路。

A - Dice

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_a

题目大意

有三个六面骰子，每个骰子的面分别写有 $1,2,3,4,5,6$ 。同时掷出这三个骰子，问朝上的点数之和能否等于 $X$ 。若可能输出 Yes，否则输出 No。其中 $1 \le X \le 20$ 。

思路

三个骰子的点数和最小为 $1+1+1=3$ ，最大为 $6+6+6=18$ 。关键在于：区间 $[3,18]$ 内的每个整数都是可以取到的——从 $(1,1,1)$ 出发，任意一个骰子每次增加 $1$ ，就能不重不漏地遍历 $3$ 到 $18$ 的所有和。因此答案是 Yes 当且仅当 $3 \le X \le 18$ 。

注意到约束中 $X$ 可以小于 $3$ 或大于 $18$ （如样例 2 的 $X=2$ ），此时直接输出 No。本题用一个条件分支即可完成，没有任何坑点。

参考代码

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

int main() {
    int X;
    cin >> X;
    if (3 <= X && X <= 18) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

X = int(input())
if 3 <= X <= 18:
    print("Yes")
else:
    print("No")

复杂度分析

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

B - 456

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_b

题目大意

有三个骰子，第 $i$ 个骰子的第 $j$ 个面上写着 $A_{i,j}$ （ $1 \le A_{i,j} \le 6$ ）。掷出后每个面朝上的概率都是 $\frac16$ 。求掷出的三个数恰好为 $4,5,6$ （各出现一次，顺序任意）的概率，相对或绝对误差不超过 $10^{-6}$ 即算正确。

思路

把每个骰子的六个面区分开来看，总结果数为 $6 \times 6 \times 6 = 216$ ，且每种结果等概率。因此只需要统计这 $216$ 种结果中有多少种满足"三个数恰好是 $\{4,5,6\}$ "：

三重循环枚举 $i,j,k$ ，取出三个数 $a_{0,i},a_{1,j},a_{2,k}$ ；
将它们排序后判断是否等于 $(4,5,6)$ （等价于它们构成的集合是 $\{4,5,6\}$ ），或者直接枚举 $6$ 种排列判断。

记满足条件的数量为 $\mathrm{cnt}$ ，答案即为 $\frac{\mathrm{cnt}}{216}$ 。由于题目要求浮点误差，输出时要用 printf("%.10f") 或 Python 的格式化输出，避免整数除法带来的截断（C++ 中务必写成 cnt / 216.0）。

参考代码

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

int main() {
    int a[3][6];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 6; j++) cin >> a[i][j];

    int cnt = 0;
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
            for (int k = 0; k < 6; k++) {
                int v[3] = {a[0][i], a[1][j], a[2][k]};
                sort(v, v + 3);
                if (v[0] == 4 && v[1] == 5 && v[2] == 6) cnt++;
            }
    printf("%.10f\n", (double)cnt / 216.0);
    return 0;
}

A = []
for _ in range(3):
    Ai = list(map(int, input().split()))
    A.append(Ai)

ans = 0
for x in A[0]:
    for y in A[1]:
        for z in A[2]:
            if sorted([x, y, z]) == [4, 5, 6]:
                ans += 1

print(f"{ans / 216:.10f}")

复杂度分析

时间复杂度： $O(6^3)=O(1)$
空间复杂度： $O(1)$

C - Not Adjacent

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_c

题目大意

给定由 a、b、c 组成的字符串 $S$ （ $|S| \le 3\times10^5$ ），求 $S$ 中没有相邻两个相同字符的非空子串个数，对 $998244353$ 取模。两个取自不同位置的子串即使内容相同也视为不同。

思路

一个子串 $S[l..r]$ 满足条件，当且仅当它不包含任何一对相邻相同字符。观察相邻位置 $i,i+1$ ：

若 $S_i \ne S_{i+1}$ ，这样的相邻对是"好"的，跨过它的子串依然可能合法；
若 $S_i = S_{i+1}$ ，任何跨越位置 $i$ 与 $i+1$ 的子串都必然含有这对相邻相同字符，一定不合法。

因此把 $S$ 在每一处 $S_i = S_{i+1}$ 的位置"切断"，得到若干内部没有相邻相同字符的极大段，一个子串合法当且仅当它完整落在某一个段内。

设一段的长度为 $L$ ，它内部任意子串都合法，个数为

\frac{L(L+1)}{2}.

对每一段求和即为答案。

注意两点：

段与段之间的边界正是 $S_i = S_{i+1}$ 的位置，合法的子串不会跨过边界；反过来，边界两侧的单字符子串分别属于两段，都被正确地计入。
答案至多为 $\frac{N(N+1)}{2} \approx 4.5\times 10^{10}$ （ $N=3\times10^5$ ），超出 32 位整数，需要用 64 位整数累加；因为整个和不超过 64 位范围，可以在最后一次性取模 $998244353$ 。

参考代码

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

int main() {
    string s;
    cin >> s;

    long long ans = 0;
    int start = 0;                       // 当前段的起始位置
    for (int i = 0; i < (int)s.size(); i++) {
        if (i + 1 == (int)s.size() || s[i] == s[i + 1]) {
            long long len = i - start + 1;
            ans += len * (len + 1) / 2;  // 该段内的子串数
            start = i + 1;
        }
    }
    cout << ans % 998244353 << '\n';
    return 0;
}

S = input()
start_i = 0
ans = 0
for i, c in enumerate(S):
    if i + 1 == len(S) or S[i + 1] == c:
        ans += (i - start_i + 1) * (i - start_i + 2) // 2
        start_i = i + 1
print(ans % 998244353)

复杂度分析

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

D - Not Adjacent 2

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_d

题目大意

给定由 a、b、c 组成的字符串 $S$ （ $|S| \le 3\times10^5$ ），求 $S$ 中没有相邻两个相同字符的非空子序列个数，对 $998244353$ 取模。两个取自不同位置组合的子序列即使内容相同也视为不同。

思路

子序列与子串的区别在于可以跳着选字符，因此 C 题的"分段"做法不再适用。这里用 DP。

设 $\mathrm{dp}[x]$ 表示：考虑已处理的前缀时，以字符 $x$ 结尾的合法非空子序列的总数（ $x \in \{a,b,c\}$ ，按位置区分）。合法子序列的限制只有"相邻字符不同"，所以"以什么结尾"是唯一需要记住的信息。

现在读入一个新字符 $c = S_i$ ，它只影响 $\mathrm{dp}[c]$ ：

不使用 $S_i$ ：原有的以 $c$ 结尾的子序列保留，贡献 $\mathrm{dp}[c]$ ；
使用 $S_i$ ：把 $S_i$ 接到任意一个以非 $c$ 字符结尾的合法子序列末尾，由于"末尾字符 $\ne c$ "保证不出现相邻相同字符，这样的子序列有 $\sum_{x \ne c}\mathrm{dp}[x]$ 个；再加上长度为 1 的单个字符子序列（即"空序列 + $S_i$ "），共 $1$ 个。

因此

\mathrm{dp}[c] \gets \mathrm{dp}[c] + \sum_{x\ne c}\mathrm{dp}[x] + 1 = \mathrm{dp}[a]+\mathrm{dp}[b]+\mathrm{dp}[c] + 1,

其中等式右边都取更新前的值。这一步同时体现了"当前字符可以选也可以不选"的两种状态，并且去重是自动的：每个子序列由"取了哪些位置"唯一确定，DP 逐位置地给每个合法子序列恰好计数一次（把它看成"最后一个被选入的位置"）。

最终答案为 $\mathrm{dp}[a]+\mathrm{dp}[b]+\mathrm{dp}[c]$ （所有非空合法子序列按其末字符归类）。所有运算对 $998244353$ 取模。

以样例 $S=$ abbc 验证：初始三个值全为 $0$ 。

处理 a： $\mathrm{dp}[a]=0+0+0+1=1$ ；
处理 b： $\mathrm{dp}[b]=1+0+0+1=2$ （b 与 ab）；
处理 b： $\mathrm{dp}[b]=1+2+0+1=4$ （保留的 b、ab，加上接到 a 后面的 b、ab 两种）；
处理 c： $\mathrm{dp}[c]=1+4+0+1=6$ 。

总和 $1+4+6=11$ ，与样例一致。

参考代码

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

int main() {
    string s;
    cin >> s;

    ll dp[3] = {0, 0, 0};          // 以 'a','b','c' 结尾的合法子序列数
    for (char c : s) {
        int id = c - 'a';
        ll sum = (dp[0] + dp[1] + dp[2]) % MOD;
        dp[id] = (sum + 1) % MOD;  // 不用当前字符 + 用当前字符
    }
    cout << (dp[0] + dp[1] + dp[2]) % MOD << '\n';
    return 0;
}

from collections import defaultdict

S = input()
dp = defaultdict(int)
for c in S:
    dp[c] = (dp['a'] + dp['b'] + dp['c'] + 1) % 998244353

print(sum(dp.values()) % 998244353)

复杂度分析

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

E - Endless Holidays

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_e

题目大意

AtCoder 王国里有 $N$ 座城市（编号 $1..N$ ）和 $M$ 条无向道路，任意两城连通。一周有 $W$ 天（ $2 \le W \le 10$ ），第 $W$ 天的下一天是第 1 天。城市 $i$ 的假日情况由长度为 $W$ 的字符串 $S_i$ 给出：第 $j$ 位是 o 表示第 $j$ 天放假，是 x 表示上班。

高桥君在第 1 天中午先任选一座城市停留，之后每天晚上可以选择留在原城市或沿一条道路走到相邻城市。问他能否无限期地安排，使得每天中午所在的城市都恰好放假。有 $T$ 组数据， $T$ 组中 $N$ 之和与 $M$ 之和均不超过 $10^5$ 。

思路

把"时间"也放进状态。设顶点 $(x,w)$ 表示"第 $w$ 天中午身处城市 $x$ "。每天夜里他可以停留在 $x$ 或走到相邻城市 $y$ ，于是下一天中午位于 $(y, w\bmod W + 1)$ 。只有当出发点与到达点在对应天都放假时，这次转移才合法：

(x,w) \to (y,\,w\bmod W+1)\quad\Longleftrightarrow\quad (x=y \text{ 或 } x,y \text{ 相邻}) \ \wedge\ S_x[w]=\texttt{o} \wedge\ S_y[w\bmod W+1]=\texttt{o}.

这样得到一个顶点数为 $N\times W$ 的有向图 $G$ （ $S_x[w]=\texttt{x}$ 的顶点没有出边）。高桥君的要求变成：是否存在一条从某个"第 1 天放假"的顶点出发的无限路径。由于图有限，无限路径必然重复访问某个顶点，从而等价于图上存在一个从起点可达的有向环。

关键观察：环长必为 $W$ 的倍数。 每走一条边，星期维度 $w$ 都恰好前进 1（模 $W$ ），沿一个长为 $L$ 的环走一圈回到起点时，星期必然回到原值，故 $L \equiv 0 \pmod W$ ，即 $L \ge W$ 。因此任何一个环都包含星期 1 的顶点（顶点的星期遍历 $1..W$ 各一次），而环上所有顶点对应天都是 o。于是：只要图 $G$ 有环，高桥君就可以从环上某个第 1 天的城市出发，沿环永远走下去；反之若图无环，任何无限路径都不可能存在。结论：

\text{答案是 } \texttt{Yes} \iff G \text{ 含有有向环。}

判环用拓扑排序（Kahn 算法）即可：统计每个顶点的入度，不断移除入度为 $0$ 的顶点；若最终移除的顶点数 $<$ 总顶点数，则存在环。x 顶点的入度、出度都为 $0$ ，会在一开始就被移除，不影响判断。每条边对应一个"城市对 + 星期"，边数约为 $(N+2M)\times W$ ，故每组数据的时间复杂度为 $O((N+M)W)$ 。

参考代码

#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;
        vector<vector<int>> adj(N + 1);
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int W;
        cin >> W;
        vector<string> S(N + 1);
        for (int i = 1; i <= N; i++) cin >> S[i];

        // 顶点 (x,w) 的编号为 (x-1)*W + (w-1)
        auto vid = [&](int x, int w) { return (x - 1) * W + (w - 1); };
        int V = N * W;

        // 统计入度
        vector<int> indeg(V, 0);
        for (int x = 1; x <= N; x++) {
            for (int w = 1; w <= W; w++) {
                if (S[x][w - 1] != 'o') continue;
                int nw = w % W + 1;                    // 下一天
                if (S[x][nw - 1] == 'o') indeg[vid(x, nw)]++;       // 原地停留
                for (int y : adj[x])
                    if (S[y][nw - 1] == 'o') indeg[vid(y, nw)]++;   // 沿道路移动
            }
        }

        // Kahn 拓扑排序判环
        queue<int> q;
        for (int v = 0; v < V; v++)
            if (indeg[v] == 0) q.push(v);
        int processed = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            processed++;
            int x = v / W + 1, w = v % W + 1;
            if (S[x][w - 1] != 'o') continue;          // x 天无出边
            int nw = w % W + 1;
            if (S[x][nw - 1] == 'o') {
                int to = vid(x, nw);
                if (--indeg[to] == 0) q.push(to);
            }
            for (int y : adj[x]) {
                if (S[y][nw - 1] == 'o') {
                    int to = vid(y, nw);
                    if (--indeg[to] == 0) q.push(to);
                }
            }
        }
        cout << (processed < V ? "Yes" : "No") << '\n';
    }
    return 0;
}

import sys
from collections import deque

input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    W = int(input())
    S = [''] + [input().strip() for _ in range(N)]

    def vid(x, w):
        return (x - 1) * W + (w - 1)

    V = N * W
    indeg = [0] * V
    for x in range(1, N + 1):
        for w in range(1, W + 1):
            if S[x][w - 1] != 'o':
                continue
            nw = w % W + 1
            if S[x][nw - 1] == 'o':
                indeg[vid(x, nw)] += 1
            for y in adj[x]:
                if S[y][nw - 1] == 'o':
                    indeg[vid(y, nw)] += 1

    q = deque(i for i in range(V) if indeg[i] == 0)
    processed = 0
    while q:
        v = q.popleft()
        processed += 1
        x = v // W + 1
        w = v % W + 1
        if S[x][w - 1] != 'o':
            continue
        nw = w % W + 1
        if S[x][nw - 1] == 'o':
            to = vid(x, nw)
            indeg[to] -= 1
            if indeg[to] == 0:
                q.append(to)
        for y in adj[x]:
            if S[y][nw - 1] == 'o':
                to = vid(y, nw)
                indeg[to] -= 1
                if indeg[to] == 0:
                    q.append(to)
    print("Yes" if processed < V else "No")

复杂度分析

时间复杂度：每组 $O((N+M)W)$ ，所有组之和 $O((\sum N+\sum M)W)$
空间复杂度：每组 $O((N+M)W)$ （显式存储图与入度）

F - Plan Holidays

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_f

题目大意

高桥君要为自己 $N$ 天的日程安排假日。初始没有假日。可以进行以下两种操作任意多次：

选一个 $i$ （ $1\le i\le N$ ），把第 $i$ 天设为假日，花费 $A_i$ ；
选一个 $i$ （ $2\le i\le N-1$ ），若第 $i-1$ 天与第 $i+1$ 天都已经是假日，则把第 $i$ 天设为假日，花费 $0$ 。

求使假日形成至少连续 $K$ 天的最小总花费。 $T$ 组数据，各组 $N$ 之和不超过 $2\times10^5$ ， $K\le N\le 2\times10^5$ ， $A_i\le 10^9$ 。

思路

第一步：把问题重述成"选择付费日"

免费操作只发生在两侧都已是假日时。分析最终假日集合的极大连续段：

每个极大连续段的两端都必须是付费日（否则端点的邻居不全是假日，不可能被免费填出）；
设两个相邻的付费日相隔 $d$ 。若 $d=1$ ，两者相邻；若 $d=2$ ，中间的这一天两侧都是假日，被免费补齐；若 $d\ge 3$ ，中间至少有两个连续工作日，它们互为"对方缺失的邻居"，永远无法被填出（陷入死锁），该段无法连通。

因此问题等价于：选择若干付费日 $p_1 < p_2 < \cdots < p_m$ ，满足相邻付费日之间至多隔 1 个工作日（即 $p_{j+1}-p_j\le 2$ ），使首尾跨度 $p_m-p_1\ge K-1$ ，并最小化 $\sum A_{p_j}$ 。此时假日连续段恰好为 $[p_1,p_m]$ ，长度为 $p_m-p_1+1$ 。

第二步：最优解只需考虑两种跨度

设 $S=p_1$ ， $T=p_m$ 。若某解满足 $T-S\ge K+1$ （连续段长度 $\ge K+2$ ），则删去最后一个付费日 $T$ ：新的末付费日 $T' \ge T-2$ ，新跨度 $T'-S \ge (T-S)-2 \ge K-1$ 仍然合法，而总花费严格减小（ $A_T>0$ ）。故最优解满足 $T-S\le K$ ，结合 $T-S\ge K-1$ 得到

T-S \in \{K-1,\ K\}.

即只需让连续段长度恰好为 $K$ 或 $K+1$ 。

第三步：固定末付费日的 DP

固定 $l$ ，令末付费日 $T = l+K-1$ ，考虑位置序列 $l-1,\,l,\,l+1,\,\dots,\,l+K-1$ （共 $K+1$ 个位置）。定义（ $A_0=\infty$ ）：

$\mathrm{dp}_0[i]$ ：考虑了位置 $l-1$ 到 $l+i-1$ 后，位置 $l+i-1$ 不是付费日（且它之前那个位置 $l+i-2$ 是付费日，从而保证相邻付费日间隔不超过 2）的最小花费；
$\mathrm{dp}_1[i]$ ：同理，位置 $l+i-1$ 是付费日的最小花费。

初值： $\mathrm{dp}_0[0]=0$ （位置 $l-1$ 不付费，把它之前的"虚拟付费日"视作已存在，对应首付费日从 $l$ 开始、跨度 $K-1$ 的情形）； $\mathrm{dp}_1[0]=A_{l-1}$ （位置 $l-1$ 付费，对应首付费日从 $l-1$ 开始、跨度 $K$ 的情形）。

转移（ $1\le i\le K$ ，位置 $p = l+i-1$ ）：

\mathrm{dp}_0[i]=\mathrm{dp}_1[i-1],\qquad \mathrm{dp}_1[i]=\min\big(\mathrm{dp}_0[i-1],\ \mathrm{dp}_1[i-1]\big)+A_p.

状态机不允许两个连续的非付费位置，恰好编码了"相邻付费日距离 $\le 2$ "。末尾必须付费，故固定 $l$ 的答案为 $\mathrm{dp}_1[K]$ 。遍历 $l=1..N-K+1$ 取最小值即可覆盖所有跨度 $K-1$ 与 $K$ 的方案。

第四步：用 min-plus 矩阵加速（核心）

直接把上述 DP 对每个 $l$ 从头跑一遍是 $O(KN)$ ，太慢。观察转移

f_a(x,y)=\big(y,\ \min(x,y)+a\big),

它等价于行向量 $(x,y)$ 在 min-plus 代数下右乘矩阵

R_a=\begin{pmatrix}\infty & a\\ 0 & a\end{pmatrix},\qquad (x',y')=(x,y)\otimes R_a,\quad (wR)_j=\min_k\,(w_k+R_{k,j}).

于是对固定 $l$ ，

(\mathrm{dp}_0[K],\mathrm{dp}_1[K])=(0,\ A_{l-1})\otimes \big(R_{A_l}\otimes R_{A_{l+1}}\otimes\cdots\otimes R_{A_{l+K-1}}\big),

其中 $\otimes$ 是 min-plus 矩阵乘法： $(A\otimes B)_{i,j}=\min_k(A_{i,k}+B_{k,j})$ 。记窗口乘积为 $H$ ，则

\mathrm{dp}_1[K]=\min\big(H_{0,1},\ A_{l-1}+H_{1,1}\big).

对每个 $l$ 都要取长度为 $K$ 的滑动窗口的矩阵乘积。由于矩阵只有 $2\times2$ ，乘积可 $O(1)$ 合并，可用分块做到总复杂度 $O(N)$ ：

把位置 $1..N$ 按块长 $K$ 分块；
对每个块预处理前缀积 $P_i=R_{\text{块首}}\otimes\cdots\otimes R_i$ 与后缀积 $S_i=R_i\otimes\cdots\otimes R_{\text{块尾}}$ ；
任一长度恰为 $K$ 的窗口 $[l,l+K-1]$ ：若 $l$ 是块首，窗口正好是一个整块，乘积为 $P_{l+K-1}$ ；否则窗口横跨两个相邻块，乘积为 $S_l\otimes P_{l+K-1}$ 。

每组的复杂度为 $O(N)$ 。用线段树做区间乘积查询则是 $O(N\log N)$ ，用 SWAG（滑动窗口聚合）同样是 $O(N)$ ，三者均可。

边界与易错点

令 $A_0=\infty$ ： $l=1$ 时"首付费日从 $l-1=0$ 开始"的方案被 $\infty$ 惩罚掉，只剩跨度 $K-1$ 的方案；
$K=1$ 时每个块长度为 1，窗口即单个位置，答案为 $\min_i A_i$ （只需一天假日），算法自动正确；
花费上界 $\sum A_i \le 2\times10^{14}$ ，用 64 位整数， $\infty$ 取 $4\times10^{18}$ 级即可。

参考代码

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

struct Mat {
    ll a[2][2];
};

// min-plus 矩阵乘法: C = A ⊗ B, C[i][j] = min_k (A[i][k] + B[k][j])
Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            C.a[i][j] = min(A.a[i][0] + B.a[0][j], A.a[i][1] + B.a[1][j]);
    return C;
}

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

    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        vector<ll> A(N + 1);
        for (int i = 1; i <= N; i++) cin >> A[i];
        A[0] = INF;

        // 按块长 K 分块
        auto blockStart = [&](int i) { return ((i - 1) / K) * K + 1; };
        auto blockEnd = [&](int i) { return min(((i - 1) / K) * K + K, N); };

        vector<Mat> pref(N + 1), suff(N + 1);
        for (int i = 1; i <= N; i++) {
            Mat m;
            m.a[0][0] = INF; m.a[0][1] = A[i];
            m.a[1][0] = 0;    m.a[1][1] = A[i];
            if (i == blockStart(i)) pref[i] = m;
            else pref[i] = mul(pref[i - 1], m);
        }
        for (int i = N; i >= 1; i--) {
            Mat m;
            m.a[0][0] = INF; m.a[0][1] = A[i];
            m.a[1][0] = 0;    m.a[1][1] = A[i];
            if (i == blockEnd(i)) suff[i] = m;
            else suff[i] = mul(m, suff[i + 1]);
        }

        ll ans = INF;
        for (int l = 1; l + K - 1 <= N; l++) {
            int r = l + K - 1;
            Mat H;
            if (l == blockStart(l)) H = pref[r];
            else H = mul(suff[l], pref[r]);
            // dp_1[K] = (0, A_{l-1}) ⊗ H 的第二个分量
            ll cand = min(H.a[0][1], A[l - 1] + H.a[1][1]);
            ans = min(ans, cand);
        }
        cout << ans << '\n';
    }
    return 0;
}

import sys

input = sys.stdin.readline
INF = 10**18

def mul(A, B):
    return [
        [min(A[0][0] + B[0][0], A[0][1] + B[1][0]),
         min(A[0][0] + B[0][1], A[0][1] + B[1][1])],
        [min(A[1][0] + B[0][0], A[1][1] + B[1][0]),
         min(A[1][0] + B[0][1], A[1][1] + B[1][1])],
    ]

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    A = [INF] + list(map(int, input().split()))

    def blockStart(i):
        return ((i - 1) // K) * K + 1

    def blockEnd(i):
        return min(((i - 1) // K) * K + K, N)

    pref = [None] * (N + 1)
    suff = [None] * (N + 1)
    for i in range(1, N + 1):
        m = [[INF, A[i]], [0, A[i]]]
        pref[i] = m if i == blockStart(i) else mul(pref[i - 1], m)
    for i in range(N, 0, -1):
        m = [[INF, A[i]], [0, A[i]]]
        suff[i] = m if i == blockEnd(i) else mul(m, suff[i + 1])

    ans = INF
    for l in range(1, N - K + 2):
        r = l + K - 1
        H = pref[r] if l == blockStart(l) else mul(suff[l], pref[r])
        cand = min(H[0][1], A[l - 1] + H[1][1])
        ans = min(ans, cand)
    print(ans)

复杂度分析

时间复杂度：每组 $O(N)$ （分块法）；也可用线段树 $O(N\log N)$ 或 SWAG $O(N)$ ，全部组的复杂度为 $O(\sum N)$ 或 $O(\sum N\log N)$
空间复杂度： $O(N)$

G - Count Holidays

题目链接：https://atcoder.jp/contests/abc456/tasks/abc456_g

题目大意

高桥君要为 $N$ 天排班，每天要么是工作日要么是假日。给定长度 $N$ 的字符串 $S$ ：第 $i$ 位是 x 表示第 $i$ 天必须是工作日，是 . 表示当天可以自由选择。设 . 的个数为 $q$ ，则共有 $2^q$ 种合法排班。

对每个 $k=1,2,\dots,N$ ，输出：在全部 $2^q$ 种排班中，最长假日连续段恰好为 $k$ 天的排班数，对 $998244353$ 取模。

思路

第一步：转化为"至多 $k$ "

设 $F(S,k)$ 为"最长假日连续段至多 $k$ 天"的排班数。若最长段恰好为 $k$ ，则是"至多 $k$ "而非"至多 $k-1$ "，故

\text{答案}(k) = F(S,k) - F(S,k-1).

第二步：按 `x` 拆分

假日连续段不可能跨越 x（x 处必须是工作日），因此把 $S$ 在 x 处切开，得到若干由 . 组成的段 $T_1,\dots,T_\ell$ （长度分别为 $n_1,\dots,n_\ell$ ），且

F(S,k) = \prod_{j=1}^{\ell} f(n_j,k),

其中 $f(n,k)$ 表示 $n$ 个连续自由日（全是 .）中，最长假日连续段至多 $k$ 天的排班数。

第三步：容斥计算 $f(n,k)$

若 $k\ge n$ ，则任何排班都满足要求， $f(n,k)=2^n$ 。下面设 $k<n$ 。

对排班定义事件 $E_d$ ："第 $d$ 天是至少 $k+1$ 天连续假日的首日"，即第 $d-1$ 天是工作日（或 $d=1$ ）且第 $d,d+1,\dots,d+k$ 天全是假日。 $f(n,k)$ 是不满足任何 $E_d$ 的排班数。记 $g(n,k,m)$ 为"选出 $m$ 个见证日 $D$ ，使得每个 $d\in D$ 都满足 $E_d$ "的（选择方式 $\times$ 排班）数量，则由容斥原理

f(n,k)=\sum_{m=0}^{\lfloor (n+1)/(k+2)\rfloor} (-1)^m\, g(n,k,m).

一个见证日 $d$ 强制了一个长度 $k+2$ 的块：第 $d-1$ 天工作日 + 第 $d\cdots d+k$ 天共 $k+1$ 天假日。两个见证日之间至少要隔 $k+2$ 天，否则后一个见证日就不是其连续假日段的首日了。按"第 1 天是否为见证日"分两类：

第 1 天不是见证日：把 $m$ 个长度 $k+2$ 的块放进 $n$ 天里，其余 $n-(k+2)m$ 天任意。 $m$ 个块起点的选取数为（标准隔板法，块起点之间至少相隔 $k+2$ ） $\binom{n-(k+1)m}{m}$ ，故贡献 $2^{\,n-(k+2)m}\,\binom{n-(k+1)m}{m}.$
第 1 天是见证日：第 $1\cdots k+1$ 天强制假日（没有前导工作日），其余 $m-1$ 个块放进第 $k+2\cdots n$ 天。块数为 $m-1$ 时起点选法为 $\binom{n-(k+1)m}{m-1}$ ，自由日数为 $n-(k+2)m+1$ ，贡献 $2^{\,n-(k+2)m+1}\,\binom{n-(k+1)m}{m-1}.$

当指数为负或组合数无定义时该项取 $0$ （约定 $\binom{a}{b}=0$ 当 $b<0$ 或 $b>a$ ）。由 $(k+2)m\le n+1$ 得 $m\le \lfloor (n+1)/(k+2)\rfloor$ 。

第四步：复杂度分析

对单个 $f(n,k)$ ，求和项数为 $O\!\left(\frac{n}{k+2}\right)$ 。对所有 $k$ 求值：

\sum_{k=0}^{n} \frac{n}{k+2} = O(n\log n).

对所有 . 段求和即得整体 $O(N\log N)$ 。组合数需要用预处理的阶乘与逆元 $O(1)$ 求， $2$ 的幂也需预计算。

最后对 $k$ 从 $1$ 到 $N$ 输出 $F(S,k)-F(S,k-1)$ 。注意当 $k$ 超过最长段长度 $L_{\max}$ 时， $F(S,k)=2^q$ 恒成立，差值恒为 $0$ ，可直接输出 $0$ 。可用 $\sum_k \text{答案}(k)=2^q-1$ （除全工作日外的每种排班恰有一个最大段长）做正确性自检。

补充（形式幂级数角度）：一个排班可以写成"若干段（ $0..k$ 个假日），工作日，（ $0..k$ 个假日）……"，其生成函数为

f(n,k)=[x^n]\sum_{i\ge 0}\frac{1-x^{k+1}}{1-x}\left(x\cdot\frac{1-x^{k+1}}{1-x}\right)^i =[x^n]\frac{1-x^{k+1}}{1-2x+x^{k+2}},

化简为 $\sum_{i\ge0}(-1)^i\dfrac{x^{(k+2)i}(1-x^{k+1})}{(1-2x)^{i+1}}$ 后，利用 $[x^m]\frac{1}{(1-2x)^{i+1}}=2^m\binom{m+i}{m}$ 同样可以 $O(n/(k+2))$ 求值，与容斥结果一致。

参考代码

#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 N;
    string S;
    cin >> N >> S;

    // 预处理阶乘、逆元、2 的幂
    vector<ll> fact(N + 1), invfact(N + 1), pow2(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[N] = modpow(fact[N], MOD - 2);
    for (int i = N; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;
    pow2[0] = 1;
    for (int i = 1; i <= N; i++) pow2[i] = pow2[i - 1] * 2 % MOD;

    auto C = [&](int n, int k) -> ll {
        if (n < 0 || k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
    };

    // 提取所有连续的 '.' 段
    vector<int> runs;
    int cnt = 0;
    for (char c : S) {
        if (c == '.') cnt++;
        else { if (cnt) runs.push_back(cnt); cnt = 0; }
    }
    if (cnt) runs.push_back(cnt);

    // f(n,k)：n 个自由日最长假日段至多 k 天
    auto f = [&](int n, int k) -> ll {
        if (k >= n) return pow2[n];
        ll res = 0;
        for (int m = 0; (ll)(k + 2) * m <= n + 1; m++) {
            ll term = 0;
            int e1 = n - (k + 2) * m;
            if (e1 >= 0)
                term = (term + pow2[e1] * C(n - (k + 1) * m, m)) % MOD;  // 第 1 天不是见证日
            int e2 = n - (k + 2) * m + 1;
            if (e2 >= 0 && m - 1 >= 0)
                term = (term + pow2[e2] * C(n - (k + 1) * m, m - 1)) % MOD;  // 第 1 天是见证日
            if (m & 1) res = (res - term) % MOD;
            else res = (res + term) % MOD;
        }
        return (res % MOD + MOD) % MOD;
    };

    int Lmax = 0;
    for (int x : runs) Lmax = max(Lmax, x);

    vector<ll> F(Lmax + 1);
    for (int k = 0; k <= Lmax; k++) {
        ll prod = 1;
        for (int n : runs) prod = prod * f(n, k) % MOD;
        F[k] = prod;
    }

    for (int k = 1; k <= N; k++) {
        if (k <= Lmax) cout << ((F[k] - F[k - 1]) % MOD + MOD) % MOD << '\n';
        else cout << 0 << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N\log N)$ （对每个 $k$ ，各段计算 $f(n,k)$ 的总开销为 $\sum_k O(n_j/(k+2))$ ，各段求和后为 $O(N\log N)$ ）
空间复杂度： $O(N)$