题意理解

我们需要统计长度为 $n$ 的 01 串 的数量，要求：

1. 以给定的 01 串 $S$（长度为 $m$）为前缀
2. 整个串中不存在任何长度为 $k$ 的平衡子串
   • 平衡子串指 0 和 1 的个数相等的子串
   • $k$ 是偶数

数据范围：$1 \le m+1 \le k \le n \le 114$

核心思路

关键观察 1：平衡串的特征

长度为 $k$（偶数）的 01 串平衡 ⇔ 该子串中 0 和 1 的个数都是 $k/2$

关键观察 2：前缀和表示

定义前缀和 $pre[i]$ 表示前 $i$ 个字符中 1 的个数减去 0 的个数。

一个子串 $[l, r]$ 平衡 ⇔ $pre[r] - pre[l-1] = 0$

因此，不存在长度为 $k$ 的平衡子串等价于： 对于所有 $i$，$pre[i] \neq pre[i-k]$

关键观察 3：状态设计

由于我们关心的是相差 $k$ 位置的前缀和关系，可以设计 DP 状态：

设 $dp[i][mask]$ 表示处理了前 $i$ 个字符，最近 $k$ 个位置的前缀和相对关系用 $mask$ 编码时的方案数。

算法框架

方法一：状压 DP（推荐）

状态设计：

• 记录最近 $k$ 个位置的前缀和差值模式
• 由于 $k \le 114$，直接记录具体值范围太大
• 但注意到我们只关心相对大小关系，可以离散化或差分编码

状态压缩： 设 $diff[i] = pre[i] - pre[i-k]$，则约束条件为所有 $diff[i] \neq 0$

状态可以用 $k$ 位来记录最近的符号模式，但 $2^k$ 太大。

优化：实际上只需要记录最近 $k-1$ 个差值符号，因为新的差值可以由旧的推导。

方法二：自动机 DP

将问题转化为在自动机上走 $n$ 步不经过非法状态：

1. 构建自动机：状态表示最近 $k-1$ 个字符
2. 非法状态：任何能形成平衡串的状态
3. DP 转移：$dp[i][state]$ 表示长度为 $i$，自动机状态为 $state$ 的方案数

状态数最多为 $2^{k-1}$，在 $k \le 20$ 时可行（子任务 2）

方法三：容斥原理

计算总方案数，减去包含至少一个平衡子串的方案数：

$$\text{答案} = \sum_{T \subseteq \text{所有可能位置}} (-1)^{|T|} \cdot f(T) $$

其中 $f(T)$ 表示在 $T$ 中所有位置都出现平衡子串的方案数。

但需要处理子串重叠的情况，比较复杂。

针对数据范围的优化

小范围 ($n \le 20$)

• 直接暴力枚举所有 $2^{n-m}$ 个可能的后缀
• 对每个候选串检查所有长度为 $k$ 的子串
• 时间复杂度：$O(2^{n-m} \cdot n)$

中等范围 ($n \le 66$)

• 使用状态压缩 DP
• 状态表示最近 $\min(k, 20)$ 个字符
• 利用 $k$ 的奇偶性优化

大范围 ($n \le 114$)

关键优化：利用平衡串的性质减少状态数

由于不能有长度为 $k$ 的平衡串，意味着：

• 任意两个相距 $k$ 的位置的前缀和不能相等
• 这限制了前缀和序列的"周期"性质

可以证明，有效状态数远小于 $2^k$

DP 转移方程

设 $dp[i][s]$ 表示前 $i$ 个字符，状态为 $s$ 的方案数。

转移：

$$dp[i+1][s'] += dp[i][s] \quad \text{如果转移合法}$$

其中状态 $s$ 编码了最近若干个字符的信息，用于检查新字符是否会产生平衡子串。

复杂度分析

• 状态数：$O(2^{\min(k, \log n)})$ 或 $O(\text{poly}(n))$
• 时间复杂度：$O(n \cdot \text{状态数})$
• 空间复杂度：$O(\text{状态数})$

在 $n \le 114$ 的范围内，经过优化的 DP 是可实现的。

实现细节

1. 前缀处理：先固定前缀 $S$，只对剩余部分计数
2. 状态编码：使用位运算压缩状态
3. 模运算：所有计算对 $998244353$ 取模
4. 边界情况：处理 $m = 0$（子任务 4）的特殊情况

总结

本题是典型的禁止模式计数问题，核心技巧包括：

1. 问题转化：将平衡串条件转化为前缀和约束
2. 状态设计：设计紧凑的状态表示来捕获关键信息
3. 算法选择：根据数据范围选择合适的算法（暴力/状压/容斥）
4. 优化技巧：利用组合性质减少状态空间

这是一个需要深刻组合洞察和精细算法实现的难题，体现了集训队互测题目的高水准。