Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n\le 2\cdot 10^7$$$, и сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^8$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Для бинарной строки$$$^{\text{∗}}$$$ $$$r$$$ определим $$$f(r)$$$ как результат следующего процесса:
Например, $$$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{‡}}$$$.
Аквавейв дал вам целое число $$$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$$$.
12123456789101001024
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}$$$.
| Codeforces Round 1046 (Div. 1) |
|---|
| Закончено |
