CF2135E2.Beyond the Palindrome (Hard Version)

这是本题的难度较高版本。本版本与另一版本的区别在于本版本有 $n\le 2\cdot 10^7$，且所有测试用例中 $n$ 的总和不超过 $10^8$。仅在你通过了所有版本的本题后，才能进行 hack。

对于一个二进制字符串 $r$，我们定义 $f(r)$ 如下：

1. 同时删除 $r$ 中所有的 $\mathtt{10}$ 子串；
2. 重复上述操作，直到 $r$ 中不含有 $\mathtt{10}$ 子串为止。

例如，$f(\mathtt{100110001}) = \mathtt{001}$，因为 $r$ 的变化如下：$\mathtt{\underline{10}01\underline{10}001} \to \mathtt{0\underline{10}01} \to \mathtt{001}$。

我们称一个二进制字符串 $s$ 是“almost-palindrome”当且仅当 $f(s)=f(\mathrm{rev}(s))$。

Aquawave 给定了一个整数 $n$。你需要帮助他计算长度为 $n$ 的本质不同的 almost-palindrome 二进制字符串的数量，答案对 $998\,244\,353$ 取模。

$*$ 二进制字符串指的是每个字符都是 $0$ 或 $1$ 的字符串。

$†$ 如果字符串 $a$ 可以通过从字符串 $b$ 的开头和结尾各删去若干个（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的子串。

$‡$ $\mathrm{rev}(s)$ 表示将字符串 $s$ 从右到左写出的结果。例如，$\mathrm{rev}(\mathtt{10100}) = \mathtt{00101}$。

每组测试数据包含若干组测试用例。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来每组测试用例一行，一个整数 $n$（$1 \le n \le 2\cdot 10^7$），表示二进制字符串的长度。

保证所有测试用例中 $n$ 的总和不超过 $10^8$。

对于每个测试用例，输出一个整数，表示长度为 $n$ 的本质不同的 almost-palindrome 二进制字符串数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，所有长度为 $1$ 的二进制字符串都是 almost-palindrome。

在第二个测试用例中，所有长度为 $2$ 的 almost-palindrome 字符串只有 $\mathtt{00}$ 和 $\mathtt{11}$。

在第三个测试用例中，所有长度为 $3$ 的 almost-palindrome 字符串有 $\mathtt{000}$、$\mathtt{010}$、$\mathtt{101}$ 和 $\mathtt{111}$。

由 ChatGPT 5 翻译