一、问题重述

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

Hard 版本数据范围：$n \le 2 \times 10^7$，所有 $n$ 之和 $\le 10^8$。

---

二、已知结论（来自 E1 和 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)$ 为：从 $(0,0)$ 到 $(n, m)$ 的路径数（步长 $(+1, +1)$ 对应 1，$(+1, -1)$ 对应 0），恰好触及直线 $y = x + l$ 和 $y = x + 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$ 为偶数。

---

四、Hard 版本的加速思路

E1 中通过枚举极差 $k = r-l$ 并利用等差数列求和，得到 $O(n \log n)$ 解法。
Hard 版本需要 $O(n)$ 预处理 + $O(1)$ 或 $O(n)$ 单次查询。

关键观察：对每个固定的 $n$，最终答案可以写成组合数 $\binom{n}{i}$ 的线性组合，系数只与 $|n-2i|$ 的某个数论函数有关。

---

五、推导最终公式（基于 Hint）

考虑所有满足 $l+r = 0$（$n$ 偶）或 $l+r = 1$（$n$ 奇）且极差 $k = r-l$ 的路径之和。
经过复杂的反射求和与交换求和次序，Hint 给出：

对于蓝色部分（即 $f(n',m',l,r)$ 的某种求和），其系数最终化简为：

$$\sum_{l} \sum_{z} \binom{n}{\frac{n - (2z-1)k}{2} - l} \quad \Rightarrow \quad \text{系数为 } g(|n-2m|) $$

其中 $g(n)$ 定义为：

$$g(n) = \sum_{d \mid n,\ 2 \nmid (n/d)} d$$

即 $n$ 的所有满足 $n/d$ 为奇数的因子 $d$ 之和。

---

六、最终封闭形式

将所有部分（主项、反射项、容斥项）求和后，得到长度为 $n$ 的几乎回文串数量为：

$$\text{ans}(n) = (-1)^{n+1} \cdot 2^n + 2 \sum_{i=0}^{n} \binom{n}{i} \big( g(|n-2i-1|) - g(|n-2i|) \big) $$

其中 $g(0)$ 需单独定义：$g(0)=0$。

---

七、进一步简化（标程实现形式）

标程中实际计算的是：

$$\text{ans} = 2 \cdot \text{sum} \pm 2^n$$

具体地：

$$\text{ans} = 2 \sum_{i=0}^{n} \binom{n}{i} \big( f(|n-2i-1|) - f(|n-2i|) \big) + \begin{cases} +2^n & n\text{ 偶} \\ -2^n & n\text{ 奇} \end{cases} $$

其中 $f(m) = g(m)$。
并且标程将组合数 $\binom{n}{i}$ 用阶乘和逆元表示，即：

$$\binom{n}{i} = \frac{n!}{i!(n-i)!}$$

---

八、数论函数 $g(n)$ 的线性筛预处理

定义 $g(n) = \sum_{d \mid n,\ 2 \nmid (n/d)} d$。
等价地，若 $n = 2^a \cdot m$（$m$ 为奇数），则：

$$g(n) = \sigma(m) \quad \text{（$m$ 的因子和）}$$

因为 $d$ 跑遍 $m$ 的所有因子乘以 $2^t$（$0 \le t \le a$），但条件 $n/d$ 为奇数要求 $d$ 必须包含全部 $2^a$，即 $d = 2^a \cdot d'$ 且 $d' \mid m$。
所以 $g(n) = 2^a \cdot \sigma(m)$。

标程中的 f[i] 实际存储的是 $g(i)$，g[i] 是辅助数组用于筛法。

筛法原理：

• 对质数 $p$：$g(p) = p + (p>2)$，即 $p=2$ 时 $g(2)=2$，$p>2$ 时 $g(p)=p+1$（因为因子 $1$ 和 $p$，且 $p/1$ 为奇数，$p/p$ 为奇数，所以 $1+p$）。
• 线性筛时，若 $i \bmod p_j = 0$，则 $i \cdot p_j$ 的 $g$ 值由 $g(i)$ 递推得到。

---

九、标程代码对应

1. 预处理（init 函数）：

   • 线性筛计算 $f[i] = g(i)$ 对 $i \le 2\times 10^7$。
   • 预处理阶乘 fac 和逆元 ifac。

2. 主循环：

   for (int i = 0; i <= n; i++) {
       ans = (ans + (ll)ifac[i] * ifac[n - i] % mod 
              * sub(f[abs(n - i * 2 - 1)], f[abs(n - i * 2)])) % mod;
   }
   ans = (ll)ans * fac[n] % mod;
   cadd(ans, ans);
   (n & 1 ? cadd : csub)(ans, qpow(2, n));
   

   • ifac[i] * ifac[n-i] 乘以 fac[n] 最后乘，等价于 $\binom{n}{i}$。
   • sub(f[abs(...)], f[abs(...)]) 计算 $g(|n-2i-1|) - g(|n-2i|)$。
   • 最后乘以 $2$ 并加上/减去 $2^n$ 对应公式中的 $2 \cdot \text{sum} \pm 2^n$。

---

十、复杂度分析

• 线性筛：$O(2\times 10^7)$
• 每个测试用例：$O(n)$ 求和
• 所有 $n$ 之和 $\le 10^8$，故总复杂度 $O(10^8)$，可接受。

---

十一、总结

Hard 版本通过：

1. 将问题转化为数论求和
2. 发现系数为 $g(m) = \sum_{d\mid m,\ 2\nmid (m/d)} d$
3. 利用线性筛 $O(\max n)$ 预处理 $g$
4. 最终 $O(n)$ 回答每个询问

实现了 $O(n)$ 总复杂度的解法，完美适配 $n \le 2\times 10^7$ 且总 $n$ 和 $\le 10^8$ 的限制。