← 返回题目列表

Codeforces · 2135/E2

E2. 超越回文(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$n\le 2\cdot 10^7$$$,并且所有测试用例的$$$n$$$总和不超过$$$10^8$$$。只有解决了该问题的所有版本,您才能破解。

对于二进制字符串$$$^{\text{*}}$$$ $$$r$$$,我们将$$$f(r)$$$定义为以下过程的结果:

  1. 从$$$r$$$同时删除所有$$$\texttt{10}$$$子字符串$$$^{\text{†}}$$$;
  2. 重复上述操作,直到$$$r$$$中不存在$$$\texttt{10}$$$子串。

例如,$$$f(\mathtt{100110001})=\mathtt{001}$$$,因为 $$$r$$$ 更改如下:$$$\mathtt{\underline{10}01\underline{10}001}\to \mathtt{0\underline{10}01}\to\mathtt{001}$$$。

我们称二进制字符串 $$$s$$$ 几乎回文 当且仅当$$$f(s)=f(\mathrm{rev}(s))$$$$$$^{\text{‡}}$$$。

Aquawave 给了你一个整数 $$$n$$$。你必须帮助他找到不同的数量 几乎回文 长度为 $$$n$$$ 的二进制字符串,以 $$$998\,244\,353$$$ 为模。

$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\texttt{0}$$$ 或 $$$\texttt{1}$$$ 的字符串。

$$$^{\text{†}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

$$$^{\text{‡}}$$$$$$\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$$$ 的二进制字符串,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

12
1
2
3
4
5
6
7
8
9
10
100
1024

输出
复制

2
2
4
8
12
26
44
86
164
302
307217648
950903700

注意

在第一个测试用例中,长度为 $$$1$$$ 的所有二进制字符串都是 几乎回文.

在第二个测试用例中,所有 几乎回文 长度为 $$$2$$$ 的二进制字符串为 $$$\mathtt{00}$$$ 和 $$$\mathtt{11}$$$。

在第三个测试用例中,所有 几乎回文 长度为 $$$3$$$ 的二进制字符串为 $$$\mathtt{000}$$$、$$$\mathtt{010}$$$、$$$\mathtt{101}$$$ 和 $$$\mathtt{111}$$$。