Beyond the Palindrome (Easy Version)

Normal form of the deletion process

The operation 10 -> empty is just stack cancellation. Scan left to right. If the next character is 0 and the top unmatched character is 1, they cancel; otherwise the character stays. The final string must be some zeros followed by some ones, because any surviving 1 before a surviving 0 would still contain 10.

Set $a_i=+1$ for 1, $a_i=-1$ for 0, and let

$p_i=\sum_{j=1}^{i}a_j,\qquad p_0=0.$

Let

$L=\min_{0\le i\le n}p_i,\qquad R=\max_{0\le i\le n}p_i,\qquad P=p_n.$

Every time the balance reaches a new negative low, that 0 cannot be matched with any earlier unmatched 1, so it survives. Therefore the number of surviving zeros in $f(s)$ is $-L$. Deletions remove equal numbers of zeros and ones, so the number of surviving ones is $P-L$. Hence

$f(s)=0^{-L}1^{P-L}.$

For $\mathrm{rev}(s)$, its prefix sums are exactly $P-p_i$ in some order. Its minimum is $P-R$, so

$f(\mathrm{rev}(s))=0^{R-P}1^R.$

Now compare the two normal forms. We need

$-L=R-P\quad\text{and}\quad P-L=R,$

and both equations say the same thing:

$P=L+R.$

So the problem is no longer about strings. It is: count length-$n$ walks with steps $+1,-1$ such that the final height equals minimum height plus maximum height.

Counting the walks

Fix the exact minimum $l$ and exact maximum $r$. We must have $l\le 0\le r$, and the final height is forced to be $l+r$.

Use a grid path view: 0 is a right step, 1 is an up step, and the balance is $y-x$. If the final balance is $l+r$, then the endpoint is

$x=\frac{n-l-r}{2},\qquad y=\frac{n+l+r}{2}.$

Invalid parity just means zero paths.

Define $F(x,y,l,r)$ as the number of paths from $(0,0)$ to $(x,y)$ that stay strictly inside the strip

$l<y-x<r.$

The reflection principle gives

$F(x,y,l,r)=\sum_{q\in\mathbb Z}\left(\binom{x+y}{x-q(r-l)}-\binom{x+y}{x-q(r-l)+r}\right),$

where out-of-range binomial coefficients are treated as $0$.

To force exact minimum $l$ and exact maximum $r$, use inclusion-exclusion. Staying between $l$ and $r$ inclusively is the same as staying strictly between $l-1$ and $r+1$, so the exact count is

$E(l,r)=F(x,y,l-1,r+1)-F(x,y,l,r+1)-F(x,y,l-1,r)+F(x,y,l,r).$

Doing this separately for every pair $(l,r)$ would be too slow. The useful compression is to group by width $k=r-l$.

For a fixed width $k$, summing one strip term over all valid $l$ makes the first binomial sweep through whole consecutive blocks. Across all reflected copies, those blocks contribute $2^n$. The reflected subtraction contributes repeated terms of the form

$k\binom{n}{\frac{n-(2q-1)k}{2}}.$

The other three inclusion-exclusion terms are the same thing shifted by one boundary. After collecting the coefficient of every $\binom{n}{i}$, the divisor sum appears.

Why? A term hits $\binom{n}{i}$ when

$|n-2i|=(\text{odd})\cdot k$

or, for the shifted terms,

$|n-2i-1|=(\text{odd})\cdot k.$

Each such width contributes weight $k$. Therefore define

$g(x)=\sum_{\substack{d\mid x\\ x/d\text{ is odd}}} d,\qquad g(0)=0.$

The final formula is

$A_n=(-1)^{n+1}2^n+2\sum_{i=0}^{n}\binom{n}{i}\left(g(|n-2i-1|)-g(|n-2i|)\right).$

That is the whole count. The scary palindrome thing got downgraded into prefix min/max, then into a divisor-weighted binomial sum. Very rude problem, but fair.

Implementation

Precompute $g$ up to $N+1$, because $|n-2i-1|$ can be $n+1$. For every possible divisor $d$, add $d$ to all numbers $d\cdot q$ where $q$ is odd:

for (int x = d; x <= N + 1; x += 2 * d) g[x] += d;

Then precompute factorials, inverse factorials, and powers of two modulo $998244353$. Each test case is a direct $O(n)$ evaluation of the formula.

Total complexity is $O(N\log N+\sum n)$, with $N=\max n$, easily fine for the easy version.