Znzryb's Blog

\documentclass{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\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}

% 保持与模板一致的 minted 样式
\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\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*{题目大意}
有 $n$ 个具有 $k$ 个面的骰子，每面的数字范围为 $0 \sim m$。需要构造一种赋值方案，使得 $i+1$ 号骰子击败 $i$ 号骰子（其中 $1 \le i < n$），并且 $1$ 号骰子击败 $n$ 号骰子。这里的“击败”定义为：两个骰子组合的 $k^2$ 种对决结果中，获胜次数严格大于一半。

同时要求在所有满足上述循环劣势条件的方案中，将 $1$ 号到 $n$ 号骰子的所有面按顺序拼接后的序列\textbf{字典序最小}。题目保证解一定存在。

\subsection*{解题思路}

这道题的核心难点在于平衡“循环劣势”与“字典序最小”这两个看似矛盾的条件。我们将推导过程分为动机分析、构造模型、条件转化和贪心求解四个部分。

\subsubsection*{1. 动机分析与核心思想}

要求最终拼接的序列字典序最小，意味着我们应当\textbf{优先让编号越小的骰子分配到越小的数字}，并且\textbf{小数字的数量应当尽可能多}。

如果我们遵循最朴素的贪心思想，直接把最小的一批数字全部分给 $1$ 号骰子，稍大一些的分给 $2$ 号骰子，以此类推，那么显然 $n$ 号骰子将拥有最大的数字。这样确实能保证 $i+1$ 击败 $i$，但会面临一个致命问题：$1$ 号骰子的数字太小，绝对无法击败 $n$ 号骰子，从而无法形成题目要求的闭环（即 $1 \to 2 \to \dots \to n \to 1$）。

为了打破这个僵局，我们必须让 $1$ 号骰子拥有\textbf{少部分非常大的数字}，大到足以在与 $n$ 号骰子的对决中获得足够的胜场。但为了不破坏字典序最小的要求，这些大的数字必须尽可能排在序列的后方。这就自然引出了“双段构造”的思想。

\subsubsection*{2. 双段构造法模型}

我们将每个骰子的 $k$ 个面拆分为两个集合：
\begin{itemize}
    \item \textbf{早段（分配较小的数字）}：设第 $i$ 号骰子的早段分配了 $x_i$ 个面。同一个骰子的所有早段面填写的数字完全相同。
    \item \textbf{晚段（分配较大的数字）}：设第 $i$ 号骰子的晚段分配了 $y_i \leftarrow k - x_i$ 个面。同一个骰子的所有晚段面填写的数字完全相同。
\end{itemize}

如你所见，为了满足“字典序最小”，我们将较小的数字优先分配给靠前的骰子，于是天然形成了两个内部递增的顺序：$\text{早段}_1 < \dots < \text{早段}_n$ 以及 $\text{晚段}_1 < \dots < \text{晚段}_n$。

但\textbf{为什么早段和晚段之间，必须是完全割裂的“所有的早段都小于所有的晚段”}（即 $\text{早段}_n < \text{晚段}_1$）呢？能不能把它们的大小关系穿插一下？

这个强行不穿插的规定，是由\textbf{“$1$ 号骰子必须击败 $n$ 号骰子”这个游戏规则倒逼出来的。}
\begin{itemize}
    \item \textbf{如果穿插了会发生什么（反证法）？} 
    假设我们不这么分，而是让 $\text{晚段}_1 < \text{早段}_n$。
    因为对于任何一个骰子来说，它的早段肯定小于它的晚段，所以 $\text{早段}_1 < \text{晚段}_1$。
    如果 $\text{晚段}_1 < \text{早段}_n$，那么对 $1$ 号骰子来说，它的\textbf{所有数字}（$\text{早段}_1$ 和 $\text{晚段}_1$）就都严格小于 $n$ 号骰子的 $\text{早段}_n$ 了。
    这意味着，$1$ 号骰子的\textbf{最大面}，都比 $n$ 号骰子的\textbf{最小面}还要小。那 $1$ 号骰子打 $n$ 号骰子的胜率直接就是 $0$，绝对不可能击败 $n$ 号。
    \item \textbf{破局的唯一方式}：
    为了让 $1$ 号能够击败 $n$ 号，$1$ 号骰子必须拥有一些能够大过 $n$ 号的数字。为了不破坏整体序列尽量小的字典序，我们把这些大数字安排在 $1$ 号骰子的末尾（也就是 $\text{晚段}_1$）。为了让这部分数字能赢过 $n$ 号，它至少必须大过 $n$ 号最小的那批数字（也就是 $\text{早段}_n$）。
    \item \textbf{贪心衔接形成最终顺序}：
    因此，$\text{晚段}_1$ 被强行拔高，必须放在 $\text{早段}_n$ 之后，即确立了不可逾越的界限：$\text{早段}_n < \text{晚段}_1$。
    而在确立了这个界限之后，剩下的数字继续按照字典序贪心法则，依次递增地分配给 $\text{晚段}_1 \to \text{晚段}_2 \to \dots \to \text{晚段}_n$。
\end{itemize}

这就是最终的全局数值大小分配顺序必须为以下形式的原因：
$$ \text{早段}_1 < \text{早段}_2 < \dots < \text{早段}_n < \text{晚段}_1 < \text{晚段}_2 < \dots < \text{晚段}_n $$

\subsubsection*{3. 胜负条件的代数推导}

任意两个骰子对决没有平局，共有 $k^2$ 种结果。要实现“击败”，获胜次数必须大于等于 $w \leftarrow \lfloor k^2/2 \rfloor + 1$。

在双段构造的大小关系下，我们来计算对决的胜场数：

\textbf{第一种情况：$1$ 号骰子击败 $n$ 号骰子}

$1$ 号的“早段”是全局最小的，无法击败 $n$ 号的任何面；
$1$ 号的“晚段”仅大于 $n$ 号的“早段”（因为 $\text{晚段}_1 < \text{晚段}_n$），因此 $1$ 号获胜的次数完全由“$1$ 号晚段”对战“$n$ 号早段”贡献。
所以 $1$ 号的总获胜次数为 $y_1 \times x_n$。我们需要满足：
$$ (k - x_1) \times x_n \ge w $$

\textbf{第二种情况：$i+1$ 号骰子击败 $i$ 号骰子（对于 $1 \le i < n$）}

\begin{itemize}
    \item $i+1$ 号的“早段”排在 $i$ 号的“早段”之后，所以能击败 $i$ 号的“早段”，贡献胜场 $x_{i+1} \times x_i$。
    \item $i+1$ 号的“晚段”排在 $i$ 号的“晚段”之后，自然也大于 $i$ 号的“早段”，所以能击败 $i$ 号的所有面，贡献胜场 $y_{i+1} \times k$。
\end{itemize}

总获胜次数要求：
$$ x_{i+1} \times x_i + y_{i+1} \times k \ge w $$
将 $y_{i+1} \leftarrow k - x_{i+1}$ 代入并化简：
$$ x_{i+1} \times x_i + k^2 - x_{i+1} \times k \ge w $$
$$ x_{i+1} \times (k - x_i) \le k^2 - w $$

为了方便，我们令常数 $R \leftarrow k^2 - w$。核心不等式即为：
$$ x_{i+1} \times (k - x_i) \le R $$

\subsubsection*{4. 贪心求解 $x_i$}

为了使字典序最小，我们需要让每个骰子尽量多地获得“早段”的容量（即小数字）。因此我们要尽可能地\textbf{最大化} $x_1$，$x_2$，$\dots$，$x_n$。

\begin{itemize}
    \item \textbf{确定 $x_1$}：根据 $1$ 击败 $n$ 的条件 $(k - x_1) \times x_n \ge w$。由于 $x_n$ 的理论最大值为 $k$，要使 $x_1$ 尽可能大，就必须让 $(k - x_1)$ 尽可能小。最极限的情况是 $x_n$ 达到最大值 $k$，此时：
    $$ (k - x_1) \times k \ge w \implies k - x_1 \ge \left\lceil \frac{w}{k} \right\rceil $$
    因此，我们贪心地取 $x_1$ 的最大合法值：
    $$ x_1 \leftarrow k - \left\lceil \frac{w}{k} \right\rceil $$

    \item \textbf{确定 $x_{i}$（对于 $i \ge 2$）}：基于不等式 $x_i \times (k - x_{i-1}) \le R$，我们要贪心地让 $x_i$ 尽可能大：
    \begin{itemize}
        \item 如果 $k - x_{i-1} > 0$，则：
        $$ x_i \leftarrow \min\left(k, \left\lfloor \frac{R}{k - x_{i-1}} \right\rfloor\right) $$
        \item 如果 $x_{i-1} \leftarrow k$，意味着 $i-1$ 号骰子全部分配为早段。此时无论 $x_i$ 取何值，$i$ 号骰子的晚段都能击败 $i-1$ 号的全部面（晚段大于一切早段）。因此可以直接贪心地让 $x_i \leftarrow k$。
    \end{itemize}
\end{itemize}

题目保证解一定存在，所以按照上述方式递推求出所有的 $x_i$ 后，我们依次给存在的早段和晚段分配严格递增的数值即可。

\subsection*{代码实现}

\begin{minted}{cpp}
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    long long n, m, k;
    if (!(cin >> n >> m >> k)) return;

    // w 为获胜所需的最少场数
    long long w = (1LL * k * k) / 2 + 1;
    // R 为推导出的常数界限
    long long R = 1LL * k * k - w;

    vector<long long> x(n + 1);
    
    // 贪心确定 1 号骰子的最大早段容量
    x[1] = k - (w + k - 1) / k; 
    
    // 递推贪心确定后续骰子的最大早段容量
    for (int i = 2; i <= n; i++) {
        long long denom = k - x[i - 1];
        if (denom == 0) {
            x[i] = k;
        } else {
            x[i] = min((long long)k, R / denom);
        }
    }

    // current_val 用于按顺序分配递增的数值
    long long current_val = 0;
    vector<long long> early_val(n + 1, -1);
    vector<long long> late_val(n + 1, -1);

    // 阶段一：按顺序给所有骰子的“早段”分配小数值
    for (int i = 1; i <= n; i++) {
        if (x[i] > 0) {
            early_val[i] = current_val++;
        }
    }
    // 阶段二：按顺序给所有骰子的“晚段”分配大数值
    for (int i = 1; i <= n; i++) {
        long long y = k - x[i];
        if (y > 0) {
            late_val[i] = current_val++;
        }
    }

    // 按照 1 到 n 号骰子的顺序，格式化输出所有的面
    bool first = true;
    for (int i = 1; i <= n; i++) {
        // 输出早段
        for (int j = 0; j < x[i]; j++) {
            if (!first) cout << " ";
            cout << early_val[i];
            first = false;
        }
        // 输出晚段
        long long y = k - x[i];
        for (int j = 0; j < y; j++) {
            if (!first) cout << " ";
            cout << late_val[i];
            first = false;
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}
\end{minted}

\subsection*{复杂度分析}
\begin{itemize}
    \item \textbf{时间复杂度}：贪心推导 $x_i$ 的过程仅需一次遍历，时间复杂度为 $\mathcal{O}(n)$。为每个面输出数值的过程需要两层循环，执行次数恰好为 $\sum_{i=1}^n x_i + y_i = n \times k$。因此总时间复杂度为 $\mathcal{O}(n \times k)$，非常高效。
    \item \textbf{空间复杂度}：存储状态数组及对应的分配数值所需的数组长度均为 $n+1$，整体占用空间为 $\mathcal{O}(n)$，能够轻松满足题目要求。
\end{itemize}

\end{document}

\documentclass{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\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}

% 保持与模板一致的 minted 样式
\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\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*{题目大意}
给定三个栈 $A, B, C$ 和两个可以暂存一个元素的变量 $L, R$（相当于两只手）。初始时栈 $A$ 中有 $n$ 个元素（从栈底到栈顶单调递减，分别为 $n, n-1, \dots, 1$），其余栈和变量均为空。要求在任意时刻各栈内都满足“越靠近栈底的元素越大”的单调性。

每次可以执行两种操作：拿起（从非空栈顶弹出一个元素，暂存到一只空闲的手中）和放下（将手中的元素压入某个栈中，需满足该栈为空或栈顶元素大于要压入的元素）。求将所有元素从 $A$ 移动到 $C$ 所需的最少“拿起”操作次数，结果对 $998244353$ 取模。

\subsection*{解题思路}

这道题的核心难点在于如何处理多出的两只手（容量为 $1$ 的栈）以及解决在递推过程中的取模比较问题。本题的正解其实是\textbf{纯递推}，我们将推导过程分为动机分析、分治转移模型、物理限制推演，以及如何突破取模困境得出最终的线性递推关系四个部分。

\subsubsection*{1. 动机分析与核心思想}

本题本质上是一个变形的多柱汉诺塔问题。经典汉诺塔中有多个容量无限的柱子，而本题中我们有三个标准栈 $A, B, C$ 和两个容量仅为 $1$ 的“退化柱” $L, R$。

面对这类求最少步数的问题，如果直接通过状态转移搜索（BFS）求解，状态空间呈指数级爆炸，对于 $10^6$ 的数据必定超时。
多柱汉诺塔问题的经典解法（即 Frame-Stewart 算法）其核心思想在于：\textbf{将整个盘子堆分为上下两部分，先借用所有空间把上部移走腾出空间，再把下部移到目标位置，最后把上部盖回来}。我们需要将这种分治递推结构完美映射到本题的条件中。

\subsubsection*{2. 经典分治法在变形汉诺塔中的映射}

根据 Frame-Stewart 算法的框架，我们要把 $A$ 栈中 $n$ 个盘子全部移到 $C$ 栈，可以分为以下三个阶段：
\begin{itemize}
    \item \textbf{第一阶段（挪开上部大山）}：我们先挑出最顶部的 $n-m$ 个较小的盘子。利用场上所有的空间（栈 $B$、$C$ 以及两只手 $L$、$R$），将这 $n-m$ 个盘子从 $A$ 栈整体搬运并堆叠到 $B$ 栈上。因为这本质上就是规模为 $n-m$ 的原问题（只是目标从 $C$ 换成了 $B$），所以这一步所需的最少“拿起”次数就是 $f_{n-m}$。
    \item \textbf{第二阶段（转移底部大盘）}：经过第一阶段，栈 $B$ 已经被较小的 $n-m$ 个盘子完全占据了。由于汉诺塔“大盘绝不能压小盘”的死规定，后续在移动剩下那些更大的盘子时，\textbf{任何大盘子都绝对不能往 $B$ 栈里放}。这就相当于栈 $B$ 在这个阶段被彻底“封印”了。我们只能利用剩下的栈 $A$、$C$ 和两只手 $L$、$R$，把最底部的 $m$ 个大盘子从 $A$ 栈搬到 $C$ 栈。我们设这种“废掉一个柱子”情况下的搬运代价为 $g_m$。
    \item \textbf{第三阶段（大山归位）}：底部大盘就位后，我们再次利用所有空间（因为大盘在 $C$ 的底部，不影响小盘放上去），把 $B$ 栈上的那 $n-m$ 个小盘子整体搬运到 $C$ 栈的顶部。这同样是一个规模为 $n-m$ 的原问题，耗费次数依然是 $f_{n-m}$。
\end{itemize}

这三个阶段衔接在一起，总的“拿起”次数就等于 $f_{n-m} + g_m + f_{n-m} = 2 \times f_{n-m} + g_m$。
为了找出将 $n$ 个盘子移走的最优方案，我们显然需要尝试所有可能的划分点 $m$，看看究竟一次性把几个大盘子留在底部转移，才能让总代价最小：
$$ f_n = \min_{m} \{2 \times f_{n-m} + g_m\} $$

\subsubsection*{3. 物理极限界限：如何用两只手极限转移 4 个盘子？}

在第二步禁用 $B$ 栈的情况下，仅靠 $A, C$ 和两只手 $L, R$，最多能移动多少个大盘子？
直觉上，废掉一根柱子，手里只能拿 2 个，加上目标柱 $C$ 必须空着接收最大的盘子，最多只能转移 $2+1=3$ 个。但这是一个巨大的物理盲点：\textbf{源柱 $A$ 本身也是可以作为中转站的！}只要严格遵守“大盘在下，小盘在上”，在最大盘子移动的瞬间，我们可以把小盘子反向压在 $A$ 栈上。

为了打破直觉盲区，我们来硬核推演一遍，如何极限榨取空间，将 4 个盘子（从底到顶为 $4, 3, 2, 1$）从 $A$ 移到 $C$：

\textbf{第一阶段：避难}
\begin{itemize}
    \item 左手 $L$ 拿 1，右手 $R$ 拿 2。（此时 $A$ 剩 $[4, 3]$）
    \item $R$ 把 2 放入 $C$，$L$ 把 1 放入 $C$。（此时 $C$ 有 $[2, 1]$，两手腾空！）
\end{itemize}

\textbf{第二阶段：抽出最大盘}
\begin{itemize}
    \item $L$ 拿 3，$R$ 拿最大的 4。
    \item \textbf{关键点}：此时 $A$ 彻底空了！最大盘 4 终于被拿在了右手 $R$ 里！
\end{itemize}

\textbf{第三阶段：极限微操，清空 $C$ 栈}
现在 $R$ 拿着 4，$L$ 拿着 3，$C$ 里面有 $[2, 1]$。我们必须把 4 放进 $C$，但两手已满，$C$ 又被占了，怎么办？利用空出来的 $A$！
\begin{itemize}
    \item $L$ 把 3 放入空的 $A$ 栈。（此时 $A$ 有 $[3]$，左手 $L$ 腾空！）
    \item $L$ 从 $C$ 拿起 1。
    \item $L$ 把 1 放入 $A$ 栈。（压在 3 上面，完全合法！此时 $A$ 有 $[3, 1]$，$L$ 再次腾空！）
    \item $L$ 从 $C$ 拿起 2。
    \item \textbf{见证奇迹的时刻}：此时 $C$ 彻底空了！$L$ 拿着 2，$R$ 拿着 4，$A$ 里安全停放着 $[3, 1]$。
\end{itemize}

\textbf{第四阶段：最大盘归位与收尾}
\begin{itemize}
    \item $R$ 把最大的 4 稳稳地放入空无一物的 $C$ 栈底部！（$C$ 有 $[4]$，$R$ 腾空）
    \item $L$ 把 2 放入 $C$ 栈。（$C$ 有 $[4, 2]$，$L$ 腾空）
    \item 最后利用两只手，把 $A$ 栈里的 $[3, 1]$ 倒腾回 $C$ 栈即可。
\end{itemize}

\textbf{为什么不能是 5 个盘子？（ $>4$ 会导致死锁的原因）}
在这个极限微操中，之所以没有卡死，是因为从 $C$ 往 $A$ 退回盘子时，我们只退回了盘子 1，压在了盘子 3 上面（$1 < 3$，完全合法）。
如果一开始试图转移的是 5 个盘子，那么在“清空 $C$ 栈”阶段，$C$ 里面将会有 $[3, 2, 1]$。当我们需要把它们退回 $A$ 栈时，我们得先拿 1 压在空出来的盘子 4 上，然后再拿 2 压在 1 上——\textbf{盘子 2 压在盘子 1 上，大盘压小盘，直接违规死锁！}
也就是说，在反向退回 $A$ 栈时，由于只能一个一个倒序拿，导致上层的盘子一定比下层的大，$A$ 栈在这个瞬间\textbf{最多只能安全地停放 1 个盘子}。加上手中能拿的 2 个盘子，以及正在转移的最大盘，物理极限刚好就是 $1 + 2 + 1 = 4$ 个！

我们通过简单的搜索即可得到 $m \le 4$ 时的常数代价：
$$g_1=1, \quad g_2=2, \quad g_3=5, \quad g_4=10$$

代入转移方程，得到了常数状态的动态规划式：
$$f_n = \min_{1 \le m \le 4} \{ 2 \times f_{n-m} + g_m \}$$

\subsubsection*{4. 纯递推的推导与取模困境的破局}

似乎到这里，我们直接写一个 $\mathcal{O}(N)$ 的循环就能通过 $10^6$ 的数据了。但这里隐藏着一个极其致命的陷阱：\textbf{取模运算与 $\min$ 操作是不兼容的！}

因为 $f_n$ 呈指数级增长，很快就会溢出 \mintinline{cpp}{long long}。如果我们为了防止溢出而在中间对结果取模，那么取模后的值再送入 $\min$ 进行大小比较，纯属荒谬（比如真实的 $10^{10} \bmod MOD$ 可能会比真实的 $10$ 还要小，导致转移决策严重错误）。

为了解决这个取模的死结，我们需要关注递推的实质：\textbf{到底在转移中，是哪个 $m$ 取到了最小值？}

我们可以用不取模的程序打印出前几十项的真实最优决策情况：
当 $n \le 7$ 时，转移处于边界调整期，其最优解为：$1, 2, 4, 6, 9, 13, 17$。
但是，\textbf{当 $n \ge 8$ 时，无一例外，所有的最优转移全部来自于 $m=4$！}

\textbf{为什么最优决策总是 $m=4$ 呢？}
其实逻辑非常直观：每挪开一次上面的“大山”（即顶部的 $n-m$ 个盘子，耗费 $2 \times f_{n-m}$），我们就应该尽可能多地把底部的盘子一次性全塞过去。而底部的容量物理极限就是 $4$ 个盘子，代价仅仅是 $g_4 = 10$。相较于呈指数级暴涨的 $f_{n-m}$，“挪开大山”的代价过于高昂，因此最大化利用底部的极限物理空间（即永远选择 $m=4$）绝对是最优的贪心策略。

这就引出了本题最终的\textbf{纯递推公式}：
当 $n \ge 8$ 时，状态转移方程完全去除了不可取模的 $\min$ 函数，退化为一个确定的、常系数线性递推方程：
$$f_n = 2 \times f_{n-4} + 10$$

有了这个严格的递推关系，取模难题迎刃而解！因为递推式中不再有任何比较操作，我们可以毫无顾忌地在每一步转移后直接取模：
$$f_n = (2 \times f_{n-4} + 10) \pmod{998244353}$$

至此，我们得到了一个完美且大道至简的 $\mathcal{O}(N)$ 纯递推解法。对于 $N = 10^6$ 的数据规模，$\mathcal{O}(N)$ 的时间复杂度能够在几毫秒内轻松跑完。即便后续遇到恶意的 $N = 10^{18}$ 的加强版数据，由于这是一个常系数线性递推，我们也可以无缝衔接\textbf{矩阵快速幂}进行对数级别的加速。但在本题的数据范围内，朴素的纯递推循环已经是最契合、最漂亮的解法。

\subsection*{代码实现}

完整代码供以验证思路：

\begin{minted}{cpp}
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;
const int MAXN = 1000000;

vector<long long> f(MAXN + 5);

void init() {
    // 阶段一：前 7 项为无规律的边界状态，Hardcode 写入
    f[1] = 1;
    f[2] = 2;
    f[3] = 4;
    f[4] = 6;
    f[5] = 9;
    f[6] = 13;
    f[7] = 17;
    
    // 阶段二：n >= 8 时，进入严格的线性递推状态
    // 最优决策固定为 m = 4，彻底避免了 min 操作与取模冲突的问题
    for (int i = 8; i <= MAXN; i++) {
        f[i] = (2 * f[i - 4] + 10) % MOD;
    }
}

void solve() {
    int n;
    cin >> n;
    cout << f[n] << "\n";
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 预处理打表，O(N) 纯递推
    init();
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}
\end{minted}

\subsection*{复杂度分析}

\begin{itemize}
    \item \textbf{时间复杂度}：通过固定最优决策点，我们将不可取模的 $\min$ 动态规划简化为了 $\mathcal{O}(N)$ 的纯线性递推。预处理阶段需执行 $N$ 次循环，时间复杂度为 $\mathcal{O}(N)$。后续每次查询直接利用数组寻址，时间复杂度为 $\mathcal{O}(1)$。总时间复杂度为 $\mathcal{O}(N + T)$，对于 $N=10^6$ 的数据规模，可以在毫秒级别内跑完。
    \item \textbf{空间复杂度}：需要一个大小为 $N$ 的一维数组来存储所有的答案表，空间复杂度为 $\mathcal{O}(N)$，占用不到 $10 \text{ MB}$，远低于题目 $65536 \text{ KB}$ 的空间限制。
\end{itemize}

\end{document}