一、问题重述

定义 $f(r)$：在二进制字符串 $r$ 中同时删除所有子串 10，重复直到无 10。
$s$ 是几乎回文当且仅当 $f(s) = f(\operatorname{rev}(s))$。
求长度为 $n$ 的几乎回文串数量，模 $998244353$。

---

二、已知结论（来自 Hint）

设 $b_i$ 为前 $i$ 个字符中 1 个数减 0 个数的值，$b_0 = 0$。
设 $l = \min b_i$，$r = \max b_i$，则 $l \le 0 \le r$。
$f(s)$ 完全由 $(l, r)$ 决定。
几乎回文条件等价于 $l + r = 0$ 当 $n$ 为偶数，$l + r = 1$ 当 $n$ 为奇数。

---

三、子问题 $f(n, m, l, r)$

定义 $f(n, m, l, r)$ 为：从 $(0,0)$ 到 $(n, m)$ 的路径数（步长 $(+1, +1)$ 对应 1，$(+1, -1)$ 对应 0），恰好触及直线 $y = x + l$ 和 $y = x + r$（即 $b_i \ge l$ 且 $b_i \le r$，且等号至少各取一次）。

Hint 给出公式：

$$f(n, m, l, r) = \sum_{k \in \mathbb{Z}} \left[ \binom{n+m}{n - k(r-l)} - \binom{n+m}{n - k(r-l) + r} \right] $$

其中 $n+m$ 为偶数（因为每步纵坐标变化 $\pm 1$）。

---

四、转化为对称形式

设 $l' = l$，$r' = r$，并令：

$$n' = \frac{n - (l+r)}{2}, \quad m' = \frac{n + (l+r)}{2} $$

则原路径映射到从 $(0,0)$ 到 $(n', m')$ 的路径，新坐标下边界为 $y = x + l$ 和 $y = x + r$ 的平移。
恰好触及上下界的路径数由容斥给出：

$$\begin{aligned} &\; f\!\left(n', m', l, r\right) \\ -&\; f\!\left(n', m', l-1, r\right) \\ -&\; f\!\left(n', m', l, r+1\right) \\ +&\; f\!\left(n', m', l-1, r+1\right) \end{aligned} $$

---

五、关键观察（压缩求和）

注意 $n' + m' = n$，且 $m' - n' = l + r$。
在 $f(n', m', l, r)$ 的展开中，二项式上指标始终为 $n'+m' = n$，与 $l, r$ 无关。
下指标为：

$$n' - k(r-l) = \frac{n - (l+r)}{2} - k(r-l)$$

以及加上 $r$ 的类似项。

固定 $k = r-l$（极差）时，$l+r$ 只有两种可能：$0$ 或 $1$（由 $n$ 奇偶性决定）。
因此对每个 $k$，只需考虑 $l+r = 0$ 和 $l+r = 1$ 两种情况，且 $l = \frac{(l+r)-k}{2}$，$r = \frac{(l+r)+k}{2}$。
此时下指标随 $p$ 变化形成等差数列，公差为 $k+2-(l+r)$（见标程中的 $k+2-t$）。

---

六、标程中的 $calc(k, t)$

标程定义 $calc(k, t)$，其中：

• $t = 0$ 对应 $l+r = 0$
• $t = 1$ 对应 $l+r = 1$

则 $l = \frac{t - k}{2}$，$r = \frac{t + k}{2}$。
代入公式后，下指标为：

$$\frac{n - t}{2} - p \cdot (k + 2 - t)$$

以及加上 $r$ 的项。
$calc(k, t)$ 的四个循环分别实现：

1. 主项 $\sum \binom{n}{...}$ 的正部分（区间和）
2. 主项中的负修正（单个组合数乘系数 $k+1-t$）
3. 反射项的正部分（区间和，从 $p=1$ 开始）
4. 反射项的负修正（单个组合数）

最终 $calc(k, t)$ 计算出固定 $k$ 和 $t$ 下的所有 $l, r$ 对应的路径数之和（即所有满足极差 $=k$ 且 $l+r=t$ 的字符串数量）。

---

七、最终答案的累加

对于每个 $k$，若 $n+k$ 为偶数（否则无合法路径），则：

• $t=0$ 的贡献为 $calc(k, 0)$
• $t=1$ 的贡献为 $calc(k, 1)$

标程中的累加方式：

cadd(ans, x);
cadd(ans, x = calc(i, 0));
y = calc(i, 1);
csub(ans, add(y, y));

其中 $x$ 初始为 $0$。
这等价于对每个 $k$，加上 $calc(k,0)$，减去 $2 \cdot calc(k,1)$。
这是因为最终答案的公式（从 Hint 4 推导）为：

$$\text{ans} = \sum_{k} \left( \text{count}_{l+r=0} - 2 \cdot \text{count}_{l+r=1} \right) $$

其中 $\text{count}_{l+r=t} = calc(k, t)$。

---

八、复杂度分析

对于每个 $k$，$calc(k, t)$ 中的循环次数约为 $O(n/k)$。
求和 $\sum_{k=1}^n n/k = O(n \log n)$。
预处理组合数 $O(n)$。
总复杂度 $O(n \log n)$，满足 $n \le 10^6$。

---

九、代码细节对应

• a[i] 存储 $\binom{n}{i}$ 模 $998244353$，s[i] 为前缀和。
• ask(l, r) 求 $\sum_{i=l}^r a[i]$。
• init 预处理逆元，用于递推组合数。
• 主循环中 for (int i = 1; i <= n; i++) 枚举极差 $k = i$。
• if (n + i & 1) continue; 确保 $n$ 与 $k$ 同奇偶，否则无合法路径。

---

十、总结

本题通过：

1. 将二进制串映射为格路
2. 利用反射原理得到恰好触及边界的路径计数公式
3. 固定极差 $k$ 并利用等差数列性质压缩求和
4. 预处理组合数及其前缀和实现 $O(n \log n)$ 查询

最终得到长度为 $n$ 的几乎回文串数量。标程完全遵循这一推导，代码中的 $calc(k, t)$ 直接实现了压缩后的求和。