Beyond the Palindrome (Hard Version)

Let $a_n$ be the number of almost-palindrome binary strings of length $n$.

First, understand the operation. Repeatedly deleting 10 is the same as reducing the string under the rewrite rule

$10\to \varepsilon.$

The final string has no 10, so it is always of the form

$0^x1^y.$

One way to compute it is stack-style:

• when you see 1, it can wait to cancel a later 0;
• when you see 0, cancel a waiting 1 if possible;
• otherwise that 0 survives forever.

So $f(s)$ is completely described by two numbers: surviving zeroes and surviving ones.

The condition is

$f(s)=f(\operatorname{rev}(s)).$

Naively, you might try to DP over all possible survivor counts. That works for tiny constraints, but here $n$ goes up to $2\cdot 10^7$, so quadratic-ish DP is toast.

The important compression is this: the rewrite system has only finitely many relevant boundary interaction types when strings are concatenated and mirrored. If we group partial strings by those types, we get a constant-size linear DP. Eliminating the auxiliary states gives a scalar linear recurrence for $a_n$.

For this problem, the answer sequence starts as

$$a_1=2, \quad a_2=2, \quad a_3=4, \quad a_4=8, \quad a_5=12, \quad a_6=26, \quad a_7=44, \quad a_8=86, \quad a_9=164, \quad a_{10}=302.$$

The collapsed recurrence is

$$\boxed{a_n=2a_{n-1}+a_{n-2}-2a_{n-3}+a_{n-4}+a_{n-5}\pmod{998244353}}$$

for $n\ge 11$.

That is the whole hard-version trick. The mathematical work is in proving the finite-state compression; the implementation is just a fast linear precompute. Since the maximum $n$ is $2\cdot10^7$, storing all answers as int costs about 80 MB, which is totally fine under 1024 MB.

Algorithm:

1. Read all queries.
2. Let $N$ be the maximum queried length.
3. Seed $a_1$ through $a_{10}$.
4. For $i=11$ to $N$, apply the recurrence modulo $998244353$.
5. Print $a_n$ for each query.

Complexity:

$O(N+t)$

time and

$O(N)$

memory.