2026 杭电春季联赛 3——1008-白茄子（一个比较 trick，但又没有那么 trick 的子序列 dp）

题目大意

题目大意

给定一个只包含字符 0 和 1 的字符串 $S$。

我们称一个序列为“茄子序列”，当且仅当该序列中逆序对的数量为奇数（在 01 序列中，逆序对数量即为子序列 10 的数量，例如 10100 有 5 个逆序对）。

对于一个序列 $S'$，定义 $f(S')$ 为：将 $S'$ 连续划分成 $k$ 个子段，使得每个子段都是“茄子序列”的最小划分段数 $k$。如果无论怎么划分都无法满足要求，则 $f(S') = 0$。

求原字符串 $S$ 的所有非空子序列（共 $2^{|S|}-1$ 个）的 $f$ 值之和。答案对 $998244353$ 取模。

数据范围

• 测试数据组数 $T \le 5$。

• 所有给定的字符串 $S$ 的总长度 $\sum |S| \le 10^7$。

样例数据

输入:
3
1100
10110010
01101001100101101001011001101001

输出:
4
160
981596155

样例解释

以第一组样例 1100 为例：
该字符串共有 $2^4 - 1 = 15$ 个非空子序列。

• 长度为 1 的子序列（两个 1，两个 0）：逆序对均为 0（偶数），无法合法划分，$f$ 值为 0。

• 长度为 2 的子序列：

  • 11 和 00：逆序对为 0，无法合法划分，$f$ 值为 0。
  • 10（共有 4 个，分别由原串位置(1,3), (1,4), (2,3), (2,4)组成）：逆序对数为 1（奇数），整个序列本身就是一个“茄子序列”，最少可划分为 1 段，因此 $f(10) = 1$。这部分 $f$ 值之和为 $4 \times 1 = 4$。

• 长度为 3 的子序列（两个 110，两个 100）：逆序对数均为 2（偶数），且无论如何划分，都无法切分成若干个逆序对均为奇数的子段，因此 $f$ 值为 0。

• 长度为 4 的子序列（1100）：逆序对数为 4（偶数），同样无法合法划分，$f$ 值为 0。

综上所述，所有非空子序列的 $f$ 值之和为 4。

思路讲解

GPT 5.4 的 latex 代码

\documentclass{article}

\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{tocloft} % 支持目录引导点
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

\begin{document}

\begin{center}
    \section*{白茄子}
\end{center}

\subsection*{题目大意}

给定一个只包含 \texttt{0} 和 \texttt{1} 的字符串 $S$。

如果一个 $01$ 序列的逆序对数量为奇数，那么称它为“茄子序列”。

对于任意一个 $01$ 序列 $T$，定义 $f(T)$ 为最小的正整数 $k$，使得我们能够把 $T$ 划分成 $k$ 个连续子段，并且每个子段都是茄子序列。如果无论如何划分都做不到，则定义 $f(T)=0$。

题目要求原串 $S$ 的所有非空子序列的 $f$ 值之和，对 $998244353$ 取模。

\subsection*{解题思路}

总长度上界达到 $10^7$，显然不可能枚举子序列，更不可能对每个子序列再跑一次分段 DP。

这道题真正要做的事情只有两步：
\begin{itemize}
    \item 先把“一个固定的 $01$ 串，它的 $f$ 值是多少”压成一个很小的自动机状态。
    \item 再在原串上做“子序列自动机 DP”，统计有多少个子序列落到每个状态。
\end{itemize}

下面从头推导这个状态。

\subsubsection*{1. 先只看一个子段，什么信息才是必要的}

如果我们只关心一个连续子段是否为茄子序列，那么真正有用的只有两个奇偶量：
\begin{itemize}
    \item $a$：当前子段中 \texttt{1} 的个数奇偶。
    \item $p$：当前子段中逆序对个数奇偶。
\end{itemize}

原因很简单。往当前子段末尾再加入一个字符时：
\begin{itemize}
    \item 如果加入的是 \texttt{1}，那么 \texttt{1} 的个数奇偶翻转，但不会新增任何逆序对。
    \item 如果加入的是 \texttt{0}，那么它会与前面所有的 \texttt{1} 形成逆序对，所以逆序对奇偶需要额外异或上“当前 \texttt{1} 的个数奇偶”。
\end{itemize}

于是转移就是：
$$
(a,p) \xrightarrow{1} (a \oplus 1,\, p)
$$
$$
(a,p) \xrightarrow{0} (a,\, p \oplus a)
$$

因此，一个“尚未结束的当前子段”只有四种内部状态：
$$
(0,0),\ (1,0),\ (0,1),\ (1,1)
$$

而一个子段是否合法，只看最后的 $p$ 是否为 $1$。也就是说，合法状态恰好是：
$$
(0,1),\ (1,1)
$$

\subsubsection*{2. 固定序列时的最优分段摘要}

固定整个序列 $T$，从左到右扫描它。上一小节已经说明，一个\textbf{未结束子段}只需要记录内部状态 $(x,y)$。而对整个前缀来说，后续字符只会继续接到最后一个未结束子段后面，因此只需要记录：最后一段的内部状态，以及前面已经结束了多少个合法段。

于是定义
$$
d_{xy}
$$
表示当前已经读完某个前缀后，在所有“最后一个未结束子段的内部状态为 $(x,y)$”的切分方案中，前面已经结束的合法子段数的最小值。

这四个量
$$
D=(d_{00},d_{10},d_{01},d_{11})
$$
合在一起，就是当前前缀的最优摘要。注意状态 $(0,0)$ 不一定表示空段，例如子段 \texttt{11} 的内部状态也会回到 $(0,0)$。

初始时我们还没有读任何字符。注意"未结束子段"允许是空串：空串里 \texttt{1} 的个数为 $0$，逆序对个数也为 $0$，所以空串的内部状态就是 $(0,0)$。此时前面没有任何已结束段，因此：
$$
d_{00}=0,\qquad d_{10}=d_{01}=d_{11}=+\infty
$$
其余三个位置都是 $+\infty$，是因为在一个字符都没有读过的时候，不可能存在一种切分方案使得最后一段的内部状态不是 $(0,0)$。

现在读下一个字符时，分成两步。

如果当前未结束子段已经合法，也就是它处于 $(0,1)$ 或 $(1,1)$，那么我们就可以选择在这里截断，让它变成一个完整答案段，然后重新开始构造下一段。

因此，在读入这个字符之前，以状态 $(0,0)$ 去承接它的最小代价为
$$
r=\min \left(d_{00},\, d_{01}+1,\, d_{11}+1\right)
$$
它对应三种来源：原来就在 $(0,0)$，或者把一个合法的 $(0,1)$、$(1,1)$ 子段截断后重新开始。

接下来再把这个字符真正接到最后一段后面。根据上一小节的单段状态转移，可得：

\textbf{如果读入的是 \texttt{0}}：
$$
\begin{cases}
d'_{00}=r\\
d'_{10}=d_{11}\\
d'_{01}=d_{01}\\
d'_{11}=d_{10}
\end{cases}
$$

\textbf{如果读入的是 \texttt{1}}：
$$
\begin{cases}
d'_{00}=d_{10}\\
d'_{10}=r\\
d'_{01}=d_{11}\\
d'_{11}=d_{01}
\end{cases}
$$

至此，对于任意一个前缀，我们都可以用四元组 $D=(d_{00},d_{10},d_{01},d_{11})$ 来概括它的最优分段信息。

整串处理结束以后，最后那个未结束子段本身也必须合法，所以只有状态 $(0,1)$ 和 $(1,1)$ 可以作为最终答案。于是：
$$
f(T)=
\begin{cases}
0, & \min(d_{01},d_{11})=+\infty\\
\min(d_{01},d_{11})+1, & \text{否则}
\end{cases}
$$

这里最后的 $+1$，就是把最后那个合法但尚未结算的子段也计入答案。也就是说，第 2 节真正得到的结论，是“一个前缀可以被四元组 $D$ 完整概括”。

\subsubsection*{3. 从“固定子序列上的 DP”到“原串上的子序列 DP”}

真正的关键跳跃就在这里。

第二节做的事情，是解决下面这个子问题：\textbf{如果某个子序列 $T$ 已经被选出来了，那么怎样在线性扫描 $T$ 的过程中求出 $f(T)$。}

在这个过程中，我们始终维护四元组
$$
D=(d_{00},d_{10},d_{01},d_{11})
$$
并且每读入一个字符 \texttt{0} 或 \texttt{1}，$D$ 都会按照固定公式转移到一个新的四元组。整串处理结束以后，$f(T)$ 也只由最终落到的这个四元组决定。

也就是说，对于一个已经选出的子序列 $T$，我们完全可以把“求 $f(T)$”理解成下面这个过程：
\begin{itemize}
    \item 初始状态是
    $$
    D_{\mathrm{start}}=(0,+\infty,+\infty,+\infty)
    $$
    \item 按顺序把 $T$ 的每个字符喂进去。
    \item 最终停在某个四元组 $D$。
    \item 再由这个 $D$ 读出 $f(T)$。
\end{itemize}

于是，子序列 $T$ 本身的具体长相其实已经不重要了。对于后续计算来说，真正重要的只有一件事：\textbf{这个子序列在第二节的 DP 里，最终会落到哪个四元组。}

这就把问题自然地转成了：\textbf{在原串 $S$ 的所有子序列中，有多少个子序列最终会落到每个四元组。}

现在从左到右扫描原串 $S$。设当前已经处理到某个前缀，定义
$$
\texttt{cnt}[D]
$$
表示这个前缀的所有子序列中，有多少个子序列在“第二节的那个 DP”里会落到状态 $D$。

初始时只有空子序列一个，它对应的状态就是起始四元组，所以：
$$
\texttt{cnt}[D_{\mathrm{start}}]=1
$$

接下来读入原串的下一个字符 $c$ 时，每个旧子序列都有且只有两种选择：
\begin{itemize}
    \item \textbf{不选}这个字符。那这个子序列本身不变，所以它在第二节 DP 里的最终状态也不变。
    \item \textbf{选}这个字符。那这个子序列就在原来的末尾多接了一个字符 $c$，因此它在第二节 DP 里的状态，会从原来的 $D$ 通过“读入一个字符 $c$”的固定转移，变成新的状态 $D'$。
\end{itemize}

这就是从“固定子序列上的 DP”跳到“原串上的子序列 DP”的根本原因：\textbf{第二节已经告诉我们，一个子序列只要知道当前四元组 $D$，再多接一个字符以后会变成什么状态就是完全确定的。}

因此我们根本不需要把每个子序列真的存下来，只需要统计每个状态里当前有多少个子序列即可。

\subsubsection*{4. 按状态统计所有子序列}

有了上一节的理解，转移就非常直接了。

假设当前扫描到字符 $c$，那么每个状态 $D$ 里的所有子序列会分成两部分：
\begin{itemize}
    \item 一部分不选 $c$，继续留在 $D$。
    \item 另一部分选 $c$，统一转移到 $\texttt{nxt}(D,c)$。
\end{itemize}

所以新的计数满足：
\begin{itemize}
    \item 不选的贡献直接保留。
    \item 选的贡献整体加到后继状态上。
\end{itemize}

当整个原串处理结束以后，所有非空子序列都会被分到某个四元组状态里。而第二节已经说明，最终状态一旦确定，$f(T)$ 也就确定了。

因此答案就是：
$$
\sum_D \texttt{cnt}[D] \times \texttt{val}(D)
$$

其中 $\texttt{val}(D)$ 表示“如果一个子序列最终落到状态 $D$，那么它的 $f$ 值是多少”。

注意空子序列也被统计进去了，但它始终停在起始状态，而起始状态对应的 $f$ 值为 $0$，所以不会对答案产生任何影响，不需要额外减掉。

最后只剩一个实现层面的问题：这样的四元组状态会不会很多？

乍一看，$d_{00},d_{10},d_{01},d_{11}$ 都可能越来越大，状态数似乎会爆炸。但实际上所有可达状态都满足下面两个不变量。

\textbf{性质一：对任意可达四元组，忽略掉 $+\infty$ 以后，剩下的有限值里一定至少有一个是 $0$。等价地说，四元组中至少有一个分量恰好等于 $0$。}

证明如下。初始状态 $(0,+\infty,+\infty,+\infty)$ 显然满足这一性质。假设当前状态满足它，讨论读入一个新字符后的下一状态：
\begin{itemize}
    \item 如果当前 $d_{00}=0$，那么 $r=0$，下一状态里自然会出现一个 $0$。
    \item 如果当前 $d_{00}\ne 0$，那么由归纳假设可知，当前四元组四个分量里至少有一个是 $0$。既然这个 $0$ 不在 $d_{00}$，那它就只能出现在 $d_{10},d_{01},d_{11}$ 之中。而这时
    $$
    \text{读入 } \texttt{0} \text{ 后的新状态为 } (r,d_{11},d_{01},d_{10}),
    $$
    $$
    \text{读入 } \texttt{1} \text{ 后的新状态为 } (d_{10},r,d_{11},d_{01}).
    $$
    也就是说，无论读入什么字符，$d_{10},d_{01},d_{11}$ 这三个值都会原样出现在下一状态中，只是位置发生了变化。因此下一状态里仍然至少有一个 $0$。
\end{itemize}

\textbf{性质二：对任意可达四元组，每个有限分量都只能是 $0,1,2$ 之一。}

我们用归纳法说明。

\begin{itemize}
    \item 初始状态是 $(0,+\infty,+\infty,+\infty)$，显然成立。
    \item 假设当前状态的所有有限值都只可能是 $0,1,2$。由性质一可知，当前四元组里至少有一个分量等于 $0$，于是
    $$
    r=\min(d_{00},\, d_{01}+1,\, d_{11}+1)
    $$
    只可能取到 $0$ 或 $1$。
    \item 下一状态的四个分量，无论读入 \texttt{0} 还是 \texttt{1}，都只是从 $r,d_{10},d_{01},d_{11}$ 这几个值里挑出来的，因此新的有限值仍然只可能是 $0,1,2$。
\end{itemize}

所以，对任意可达状态，每个分量都只可能属于集合
$$
\{+\infty,0,1,2\}
$$

这就直接说明状态数不可能爆炸。因为四个位置每个都只有常数种取值，理论上状态总数至多是
$$
4^4=256
$$
个，实际上再结合“至少有一个有限值为 $0$”这一条件，还会更少。

于是，从初始状态
$$
(0,+\infty,+\infty,+\infty)
$$
出发，把 \texttt{0} 和 \texttt{1} 两种转移都不断展开，实际可达状态总共只有 $40$ 个。

这个常数已经很小了，所以实现时直接对这 $40$ 个状态做上一段的子序列计数 DP 即可，完全没有必要再继续压缩状态。

\subsection*{代码实现}

下面给出完整实现。代码会在程序启动时自动构造这 $40$ 个可达状态，之后对每个测试串做线性 DP。

\subsubsection*{实现指导}

如果直接照着上面的思路写代码，最容易卡住的地方主要有两个：第一是如何把这 $40$ 个状态真正枚举出来，第二是如何把“选或不选”的子序列 DP 和状态转移接起来。一个比较顺手的实现顺序如下。

\begin{itemize}
    \item \textbf{先把单个状态的转移写出来。}用 \texttt{State = array<int, 4>} 表示四元组，顺序固定为 \texttt{(d00, d10, d01, d11)}。然后写两个辅助函数：
    \begin{itemize}
        \item \texttt{move\_state(d, bit)}：把第二节的转移公式原样翻译成代码，输入旧状态和新字符，输出新状态。
        \item \texttt{get\_value(d)}：根据最终状态 $d$ 读出这个子序列的 $f$ 值，也就是 $\min(d_{01},d_{11})+1$ 或 $0$。
    \end{itemize}

    \item \textbf{再用 BFS 枚举所有可达状态。}从初始状态 \texttt{\{0, INF, INF, INF\}} 出发。用
    \begin{itemize}
        \item \texttt{states} 存所有已经发现的状态，
        \item \texttt{id[state]} 记录每个状态的编号，
        \item \texttt{queue} 按 BFS 方式扩展。
    \end{itemize}
    每次弹出一个状态后，分别尝试读入 \texttt{0} 和 \texttt{1}，得到两个后继状态；如果某个后继状态还没出现过，就分配新编号并入队。这样就能把整张状态图一次性建出来。

    \item \textbf{然后写子序列计数 DP。}设 \texttt{dp[q]} 表示：当前已经扫描完原串某个前缀后，有多少个子序列会落到状态 \texttt{q}。初始时只有空子序列存在，所以只有起始状态的计数是 $1$。
    
    当读到一个新字符时：
    \begin{itemize}
        \item 不选这个字符，状态不变，所以可以先令 \texttt{ndp = dp}。
        \item 选这个字符，那么原来在状态 \texttt{q} 的所有子序列，都会一起转移到 \texttt{nxt[q][bit]}，于是把 \texttt{dp[q]} 累加过去即可。
    \end{itemize}
    扫描完整个字符串后，再把所有状态上的 \texttt{dp[q] * val[q]} 累加起来，就是答案。

    \item \textbf{最后在 \texttt{main()} 里先预处理一次，再回答所有询问。}由于状态图只和题目规则有关，与具体输入字符串无关，所以 \texttt{build\_automaton()} 只需要调用一次。之后每组测试数据单独调用 \texttt{solve\_one()} 即可。
\end{itemize}

\begin{minted}{cpp}
#include <bits/stdc++.h>
using namespace std;

static constexpr int MOD = 998244353;
static constexpr int INF = (int)1e9;

using State = array<int, 4>; // 顺序为 d00, d10, d01, d11

struct Automaton {
    int start = 0;
    vector<array<int, 2>> nxt;
    vector<int> val; // 该状态对应的 f(T)
};

int add_one(int x) {
    return x >= INF ? INF : x + 1;
}

// 在“固定串最少分段 DP”里，读入一个新字符后的状态转移
State move_state(const State& d, int bit) {
    int restart = min({d[0], add_one(d[2]), add_one(d[3])});
    if (bit == 0) {
        return State{restart, d[3], d[2], d[1]};
    } else {
        return State{d[1], restart, d[3], d[2]};
    }
}

// 当前状态本身对应的 f(T)
int get_value(const State& d) {
    int best = min(d[2], d[3]);
    return best >= INF ? 0 : best + 1;
}

// 从初态出发，BFS 枚举所有可达状态
Automaton build_automaton() {
    vector<State> states;
    vector<array<int, 2>> nxt;
    vector<int> val;
    map<State, int> id;
    queue<int> q;

    auto get_id = [&](const State& s) -> int {
        auto it = id.find(s);
        if (it != id.end()) return it->second;
        int nid = (int)states.size();
        id[s] = nid;
        states.push_back(s);
        nxt.push_back({0, 0});
        val.push_back(0);
        q.push(nid);
        return nid;
    };

    Automaton aut;
    aut.start = get_id(State{0, INF, INF, INF});

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        val[u] = get_value(states[u]);
        for (int bit = 0; bit < 2; ++bit) {
            State ns = move_state(states[u], bit);
            nxt[u][bit] = get_id(ns);
        }
    }

    aut.nxt = move(nxt);
    aut.val = move(val);
    return aut;
}

int solve_one(const string& s, const Automaton& aut) {
    int m = (int)aut.nxt.size();
    vector<int> dp(m, 0), ndp(m, 0);

    // 空子序列
    dp[aut.start] = 1;

    for (char ch : s) {
        int bit = ch - '0';

        // 不选当前字符
        ndp = dp;

        // 选当前字符
        for (int q = 0; q < m; ++q) {
            if (dp[q] == 0) continue;
            int nq = aut.nxt[q][bit];
            ndp[nq] += dp[q];
            if (ndp[nq] >= MOD) ndp[nq] -= MOD;
        }

        dp.swap(ndp);
    }

    long long ans = 0;
    for (int q = 0; q < m; ++q) {
        ans = (ans + 1LL * dp[q] * aut.val[q]) % MOD;
    }
    return (int)ans;
}

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

    Automaton aut = build_automaton();

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        cout << solve_one(s, aut) << '\n';
    }
    return 0;
}
\end{minted}

\subsection*{复杂度分析}

\begin{itemize}
    \item \textbf{预处理复杂度}：从初态出发 BFS 枚举可达状态，状态总数只有 $40$ 个，因此预处理复杂度是 $\mathcal{O}(1)$。
    \item \textbf{单组时间复杂度}：设可达状态数为 $m=40$，扫描每个字符时做一次大小为 $m$ 的 DP，故时间复杂度为 $\mathcal{O}(40 \times |S|)$，也就是线性复杂度。
    \item \textbf{总时间复杂度}：$\mathcal{O}\!\left(40 \times \sum |S|\right)$。
    \item \textbf{空间复杂度}：自动机和 DP 数组都只有常数大小，空间复杂度为 $\mathcal{O}(1)$。
\end{itemize}

\subsection*{小结}

这道题最难的地方，不是最后的子序列 DP，而是先把“最少分段数”这个看起来很全局的量压成一个很小的自动机状态。

一旦完成了这一步，后面的部分就会变成非常标准的套路：\textbf{子序列计数 + 自动机转移}。整个算法的本质，就是先把复杂条件局部化，再把所有子序列统一交给自动机去分类统计。

\end{document}

PDF

我们先看段，再看串，最后看如何前缀 dp。（注意，所谓的串，是假设我们已经从原字符串取出来了一个子序列，我们称其为串，而段，是对这个串进行分段以后的这个段。）

上面其实讲的事情很简单，就是说一个段，可以用 1 的数量和逆序对数量来表征。

那么，怎么样求一个串的最优分段数量呢？

struct State {
    // d[num1][rev] 表示当前已经读完某个前缀后，
    // num1 就是1的个数的奇偶性，rev 就是 逆序对 数量
    // 在所有“最后一个未结束子段的内部状态为 $(x,y)$”的切分方案中，前面已经结束的合法子段数的最小值。
    // num1，rev 代表未结束子串状态，未结束子串允许是空串
    array<array<ll, 2>, 2> d;

    auto operator<=>(const State &) const = default;

    [[nodiscard]] State next_state(ll op) const {
        array<array<ll, 2>, 2> nd{INF, INF, INF, INF};
        for (int num1 = 0; num1 < 2; ++num1) {
            for (int rev = 0; rev < 2; ++rev) {
                ll to_num1 = num1 ^ op, to_rev = rev ^ (op == 0 ? num1 : 0);
                nd[to_num1][to_rev] = min(nd[to_num1][to_rev], d[num1][rev]);
                if (rev == 1) {
                    nd[op][0] = min(nd[op][0], d[num1][rev] == INF ? INF : d[num1][rev] + 1);
                }
            }
        }
        return State{nd};
    }
};

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=18676

源代码

// teamname: Gospel_rock
/**
 * Problem: 白茄子
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1199&pid=1008
 * Created: 2026-04-09 13:13:03
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
ll add_one(ll x) {
    if (x == INF) return INF;
    return x + 1;
}

struct State {
    // d[num1][rev] 表示当前已经读完某个前缀后，
    // num1 就是1的个数的奇偶性，rev 就是 逆序对 数量
    // 在所有“最后一个未结束子段的内部状态为 $(x,y)$”的切分方案中，前面已经结束的合法子段数的最小值。
    // num1，rev 代表未结束子串状态，未结束子串允许是空串
    array<array<ll, 2>, 2> d;

    auto operator<=>(const State &) const = default;

    [[nodiscard]] State next_state(ll op) const {
        array<array<ll, 2>, 2> nd{INF, INF, INF, INF};
        for (int num1 = 0; num1 < 2; ++num1) {
            for (int rev = 0; rev < 2; ++rev) {
                ll to_num1 = num1 ^ op, to_rev = rev ^ (op == 0 ? num1 : 0);
                nd[to_num1][to_rev] = min(nd[to_num1][to_rev], d[num1][rev]);
                if (rev == 1) {
                    nd[op][0] = min(nd[op][0], d[num1][rev] == INF ? INF : d[num1][rev] + 1);
                }
            }
        }
        // 这个 state 应该是最优的
        return State{nd};
    }
};

struct Automation {
    ll idx = 0;
    vector<array<ll, 2> > nxt;
    map<State, ll> mp;
    vector<State> idx_state;

    Automation() {
        idx_state.resize(50);
        nxt.resize(50, {-1, -1});
        queue<State> q;
        q.push({0, INF, INF, INF});
        mp[q.back()] = idx;
        idx_state[idx] = q.back();
        ++idx;
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (int i = 0; i < 2; ++i) {
                auto v = u.next_state(i);
                if (mp.contains(v)) {
                    nxt[mp[u]][i] = mp[v];
                    continue;
                }
                mp[v] = idx;
                idx_state[idx] = v;
                nxt[mp[u]][i] = idx;
                ++idx;
                q.push(v);
            }
        }
        // #ifdef LOCAL
        //         // idx = [40]
        //         debug(idx);
        // #endif
    }
};

struct Solve {
    ll N;
    string s;
    // dp[status] 应该是指该状态下有多少个这个子序列吧
    vector<ll> dp;
    static inline Automation aut;
    // static inline const auto &nxt = aut.nxt;

    Solve() {
        // cin >> N;
        cin >> s;
        N = SZ(s);
        dp.resize(50);
        dp[0] = 1;
        vector<ll> ndp;
        for (int i = 0; i < N; ++i) {
            ll ch = s[i] - '0';
            ndp = dp;
            for (int status = 0; status <= 45; ++status) {
                ll to_status = aut.nxt[status][ch];
                if (to_status == -1) continue;
                ndp[to_status] += dp[status];
                ndp[to_status] %= mod;
            }
            // swap(ndp, dp);
            dp.swap(ndp);
        }
        ll ans = 0;
        for (int status = 0; status <= 45; ++status) {
            if (dp[status] == 0) continue;
            State state = aut.idx_state[status];
            const auto &d = state.d;
            ll lans = INF;
            for (int num1 = 0; num1 < 2; ++num1) {
                if (d[num1][1] == INF) continue;
                ll val = d[num1][1] + 1;
                lans = min(lans, val * dp[status]);
            }
            if (lans == INF) continue;
            ans += lans;
            ans %= mod;
        }
        cout << ans << "\n";
        // mod
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve solve;
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=18676

*/

心路历程（WA，TLE，MLE……）

注意，不要在循环内新建这个变量，可以把这个变量放在外面（说白了就是建内存块，delete 析构内存慢）

注意在构造 nxt 数组的时候，一定不要忘记给已经到过的点也要建边

注意，防止哨兵值参与计算，如果是 INF 哨兵值，就直接 continue

latex 错误报告代码

\documentclass{article}

\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{tocloft} % 支持目录引导点
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

% 与原先 listings 外观大致对齐；
\setminted{
	% 允许长行换行
	breaklines=true,
	% 允许在任意位置换行，防止长 URL 戳出去
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

% --- 目录样式修改 ---
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}} % 让 section 也有点点
% ------------------

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref} % 添加超链接和PDF书签支持

\begin{document}

\begin{center}
{\LARGE\textbf{「白茄子」调试错误总结报告}}\\[0.5em]
{\large HDU 2026 杭电春季联赛 3 · 1008}\\[0.3em]
{\normalsize 2026-04-09}
\end{center}

\vspace{1em}

\noindent 本文档记录了在使用「DFA 状态自动机 + 子序列计数 DP」解法实现「白茄子」一题过程中所犯的全部错误，涵盖正确性错误（WA）与性能错误（TLE），并逐一给出错因分析与修复方案。

\tableofcontents
\newpage

%======================================================================
\section{错误一：\texttt{next\_state} 中修改了循环变量}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
[[nodiscard]] State next_state(ll op) const {
    array<array<ll, 2>, 2> nd{INF, INF, INF, INF};
    for (int num1 = 0; num1 < 2; ++num1) {
        for (int rev = 0; rev < 2; ++rev) {
            ll to_num1 = num1, to_rev = rev;
            if (op == 0) to_rev ^= num1;
            if (op == 1) num1 ^= 1;       // 错误：修改了循环变量 num1
            nd[to_num1][to_rev] = min(nd[to_num1][to_rev], d[num1][rev]);
            // ...
        }
    }
    return State{nd};
}
\end{minted}

\subsection*{错误分析}
\texttt{if (op == 1) num1 \^{}= 1;} 本意是计算"追加字符 \texttt{1} 后 \texttt{1} 的个数奇偶性翻转"，结果应写入 \texttt{to\_num1}。但代码直接修改了外层循环变量 \texttt{num1}，导致：

\begin{itemize}
\item 后续对 \texttt{d[num1][rev]} 的读取使用了被篡改的 \texttt{num1}，读到的是错误的源状态。
\item 循环变量被翻转后，整个遍历顺序被打乱——当 \texttt{op = 1} 时，内层循环对 \texttt{num1 = 0} 的两次迭代实际上分别使用了 \texttt{num1 = 0} 和 \texttt{num1 = 1}，完全混乱。
\end{itemize}

\subsection*{修复}
\begin{minted}{cpp}
ll to_num1 = num1 ^ op, to_rev = rev ^ (op == 0 ? num1 : 0);
\end{minted}

用一行表达式直接计算目标状态，彻底避免对循环变量的修改。

\subsection*{教训}
永远不要在循环体内修改循环变量的值（除非是有意的 \texttt{++i} 式跳步）。当需要基于循环变量做变换时，应使用独立的临时变量存储变换结果。

%======================================================================
\section{错误二：\texttt{next\_state} 中截断条件写反}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int num1 = 0; num1 < 2; ++num1) {
    for (int rev = 0; rev < 2; ++rev) {
        // ... 不截断的转移 ...
        if (rev == 0) {   // 错误：应该是 rev == 1
            nd[op][0] = min(nd[op][0],
                d[num1][rev] == INF ? INF : d[num1][rev] + 1);
        }
    }
}
\end{minted}

\subsection*{错误分析}
截断操作的含义是"把当前未结束子段关闭为一个完整的茄子序列段"。一个子段是茄子序列当且仅当其逆序对数为奇数，即内部状态中 \texttt{rev = 1}。因此只有 \texttt{rev == 1} 的子段才有资格被截断。

代码中 \texttt{if (rev == 0)} 恰好写反了：它允许逆序对数为偶数（非茄子序列）的子段被截断，却禁止了真正合法的子段被截断。

\subsection*{修复}
\begin{minted}{cpp}
if (rev == 1) {   // 正确：只有茄子序列（rev 为奇）才能截断
    nd[op][0] = min(nd[op][0],
        d[num1][rev] == INF ? INF : d[num1][rev] + 1);
}
\end{minted}

\subsection*{教训}
涉及"合法性判定"的条件分支，写完后必须回到定义逐字核对。本题中"茄子序列 $\Leftrightarrow$ 逆序对为奇 $\Leftrightarrow$ \texttt{rev == 1}"，写成 \texttt{rev == 0} 属于最基本的条件取反错误。

%======================================================================
\section{错误三：BFS 建自动机时 \texttt{nxt} 表不完整}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < 2; ++i) {
    auto v = u.next_state(i);
    if (mp.contains(v)) {
        continue;   // 错误：跳过了，但没有记录转移边
    }
    mp[v] = idx;
    nxt[mp[u]][i] = idx;
    ++idx;
    q.push(v);
}
\end{minted}

\subsection*{错误分析}
当目标状态 \texttt{v} 已经在 BFS 中被访问过时，代码直接 \texttt{continue}，\textbf{没有设置 \texttt{nxt[mp[u]][i] = mp[v]}}。这导致所有"转移到已访问状态"的边全部留为初始值 $-1$。

自动机共 $40$ 个状态、$80$ 条有向边，但其中只有 $39$ 条（BFS 树边）被正确记录，剩下 $41$ 条（回边和交叉边）全部丢失。后续的子序列 DP 在遇到这些 $-1$ 的转移时会直接跳过，导致大量合法的子序列转移被忽略。

\subsection*{修复}
\begin{minted}{cpp}
for (int i = 0; i < 2; ++i) {
    auto v = u.next_state(i);
    if (!mp.contains(v)) {
        mp[v] = idx;
        idx_state[idx] = v;
        ++idx;
        q.push(v);
    }
    nxt[mp[u]][i] = mp[v];   // 无论 v 是否新发现，都要记录转移
}
\end{minted}

\subsection*{教训}
BFS 建图时，"发现新节点"和"记录边"是两个独立的操作。即使目标节点已经在队列中，从当前节点到它的\textbf{转移边}仍然必须被记录。这是 BFS 建自动机的经典易错点。

%======================================================================
\section{错误四：子序列 DP 缺少取模}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int status = 0; status <= 45; ++status) {
    ll to_status = aut.nxt[status][ch];
    if (to_status == -1) continue;
    ndp[to_status] += dp[status];   // 错误：没有取模
}
\end{minted}

\subsection*{错误分析}
题目要求答案对 $998244353$ 取模。\texttt{dp[status]} 本身已经是模意义下的值（$< 998244353 < 10^9$），但多次累加后 \texttt{ndp[to\_status]} 可能超过 \texttt{long long} 的范围。更关键的是，不取模会导致后续与 $f$ 值相乘时溢出，产生完全错误的结果。

\subsection*{修复}
\begin{minted}{cpp}
ndp[to_status] += dp[status];
if (ndp[to_status] >= mod) ndp[to_status] -= mod;
\end{minted}

由于每次只加一个 $< \text{mod}$ 的值，和一定 $< 2 \times \text{mod}$，用一次减法代替取模运算，在 $10^7$ 的循环量级下更快。

\subsection*{教训}
模意义下的 DP，每一步累加都必须取模。即使中间结果不溢出 \texttt{long long}，不取模也会导致后续乘法溢出或数值语义错误。

%======================================================================
\section{错误五：答案计算对 $f$ 值求和而非取最小值}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int num1 = 0; num1 < 2; ++num1) {
    if (d[num1][1] == INF) continue;
    ll val = d[num1][1] + 1;
    ans += val * dp[status];   // 错误：把两个候选值都加进去了
    ans %= mod;
}
\end{minted}

\subsection*{错误分析}
对于一个自动机状态 $D = (d_{00}, d_{10}, d_{01}, d_{11})$，其对应的 $f$ 值应为
$$
f = \min(d_{01}+1,\; d_{11}+1)
$$
即在所有合法（$\texttt{rev}=1$）的末段中，选择已结束段数最少的方案，再加上末段本身的 $1$ 段。

但代码中用 \texttt{for} 循环遍历 \texttt{num1 = 0, 1}，把 $d_{01}+1$ 和 $d_{11}+1$ \textbf{都}乘以 \texttt{dp[status]} 加到了答案里。当两者同时有限时（例如 $d_{01} = 0, d_{11} = 1$），正确的 $f = 1$，但代码计算出 $(0+1) + (1+1) = 3$，严重偏大。

\subsection*{修复}
\begin{minted}{cpp}
ll lans = INF;
for (int num1 = 0; num1 < 2; ++num1) {
    if (d[num1][1] == INF) continue;
    ll val = d[num1][1] + 1;
    lans = min(lans, val);   // 取最小值
}
if (lans == INF) continue;
ans += lans % mod * dp[status] % mod;
ans %= mod;
\end{minted}

\subsection*{教训}
$f$ 的定义是"最小划分段数"，涉及最小值。在最终统计时必须对所有候选方案取 $\min$，而非求和。这是把"最优化问题"和"计数问题"的操作搞混了。

%======================================================================
\section{错误六：答案计算缺少 $+\infty$ 守卫}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
ll lans = INF;
for (int num1 = 0; num1 < 2; ++num1) {
    if (d[num1][1] == INF) continue;
    ll val = d[num1][1] + 1;
    lans = min(lans, val);
}
// 缺少：if (lans == INF) continue;
ans += lans % mod * dp[status] % mod;
ans %= mod;
\end{minted}

\subsection*{错误分析}
当某个自动机状态 $D$ 的 $d_{01}$ 和 $d_{11}$ 均为 $+\infty$ 时，意味着落在该状态的子序列无法完成合法划分，其 $f$ 值为 $0$，不应对答案有任何贡献。

但如果缺少 \texttt{if (lans == INF) continue;}，\texttt{lans} 仍为初始值 \texttt{INF}（$= 2^{61} - 1$），这个巨大的数值会被乘以 \texttt{dp[status]} 后加入答案，导致结果完全错误。

\subsection*{修复}
\begin{minted}{cpp}
if (lans == INF) continue;   // f=0 的状态不贡献答案
\end{minted}

\subsection*{教训}
使用哨兵值（如 \texttt{INF}）初始化 \texttt{min} 变量时，计算结束后必须检查结果是否仍为哨兵值。如果是，说明没有任何有效候选，必须跳过后续计算，否则哨兵值会作为"正常数值"参与运算。

%======================================================================
\section{错误七（TLE）：循环内 \texttt{vector} 拷贝构造导致 $10^7$ 次堆分配}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < N; ++i) {
    ll ch = s[i] - '0';
    vector<ll> ndp = dp;   // 拷贝构造：每次都 new 一块内存
    for (int status = 0; status <= 45; ++status) {
        // ...
    }
    swap(ndp, dp);
}   // ndp 析构：每次都 delete 一块内存
\end{minted}

\subsection*{错误分析}
\texttt{vector<ll> ndp = dp;} 是拷贝构造，每次调用都会在堆上分配 $50 \times 8 = 400$ 字节的新内存，循环结束时 \texttt{ndp} 析构又将其释放。$N$ 最大为 $10^7$，因此总共触发 $10^7$ 次 \texttt{malloc} + $10^7$ 次 \texttt{free}，系统调用开销远超 DP 本身的计算量。

\subsection*{修复}
将 \texttt{ndp} 的声明提到循环外部，循环内用赋值代替构造：

\begin{minted}{cpp}
vector<ll> ndp;              // 提到循环外
for (int i = 0; i < N; ++i) {
    ll ch = s[i] - '0';
    ndp = dp;                // 赋值：size 相同时不会重新分配内存
    for (int status = 0; status <= 45; ++status) {
        // ...
    }
    dp.swap(ndp);            // O(1)，只交换内部指针
}
\end{minted}

当 \texttt{ndp} 和 \texttt{dp} 的 \texttt{size} 相同时，\texttt{ndp = dp} 只做 \texttt{memcpy}，不触发堆分配。而 \texttt{swap} 只交换三个指针，开销为 $O(1)$。整个循环从 $10^7$ 次堆操作降为 $0$ 次。

\subsection*{教训}
在热循环（$\ge 10^6$ 次）中，绝对不能使用会触发堆内存分配的操作。\texttt{vector} 的拷贝构造、\texttt{push\_back} 触发扩容、\texttt{= \{\}} 赋空值释放内存，都是常见的隐性性能杀手。应优先使用 \texttt{clear()} 保留容量、预分配 + 赋值复用、或直接使用定长数组。

%======================================================================
\section{错误总览}
%======================================================================

\begin{center}
\renewcommand{\arraystretch}{1.4}
\begin{tabular}{c|l|c|c}
\hline
\textbf{编号} & \textbf{错误描述} & \textbf{类型} & \textbf{后果} \\
\hline
1 & \texttt{next\_state} 修改循环变量 \texttt{num1} & 逻辑 & WA \\
2 & 截断条件 \texttt{rev==0} 应为 \texttt{rev==1} & 逻辑 & WA \\
3 & BFS 未记录到已访问状态的转移边 & 遗漏 & WA \\
4 & 子序列 DP 累加后未取模 & 遗漏 & WA \\
5 & $f$ 值对两个候选求和而非取 $\min$ & 语义 & WA \\
6 & 缺少 $+\infty$ 守卫导致哨兵值参与计算 & 遗漏 & WA \\
7 & 循环内 \texttt{vector} 拷贝构造触发 $10^7$ 次堆分配 & 性能 & TLE \\
\hline
\end{tabular}
\end{center}

\end{document}

PDF