「自指01序列」题解

问题分析

我们需要计算长度为 $n$ 的 0-1 序列 $s$ 的数量，满足：

• 对于每个长度为 $k$ 的连续子段（共 $n-k+1$ 个）
• 将该子段看作 $k$ 位二进制数（左侧高位，右侧低位），设为 $t$
• 要求 $s_t = 1$（即序列的第 $t$ 位必须是 1）

换句话说，序列 $s$ 必须满足：

$$\forall i \in [0, n-k], \quad s_{\text{bin}(s_i s_{i+1} \cdots s_{i+k-1})} = 1 $$

其中 $\text{bin}(x)$ 表示将二进制串 $x$ 转换为十进制数。

关键约束

设窗口 $w_i = s_i s_{i+1} \cdots s_{i+k-1}$ 对应的数值为 $t_i$，则要求 $s_{t_i} = 1$。

这意味着：每个长度为 $k$ 的窗口对应的数值，必须是一个 1 的位置索引。

重新理解问题

我们可以将序列 $s$ 看作一个有向图上的路径：

1. 状态表示

考虑一个滑动窗口，当前窗口内容是 $k$ 位二进制数。当我们向右移动一位时，窗口内容从 $x$ 变为：

• 去掉最高位，左移一位
• 加上新的最低位 $b \in \{0,1\}$

即：$(x \ll 1) \& \text{mask} + b$，其中 $\text{mask} = 2^k - 1$。

因此，我们可以将每个 $k$ 位二进制数看作一个状态，共 $2^k$ 个状态。

2. 转移条件

设当前窗口对应的数值（状态）为 $t$，那么根据条件，$s_t$ 必须是 1。

但 $s_t$ 是什么？$t$ 是当前窗口的数值，而 $s_t$ 是序列第 $t$ 位的值。这个值会影响未来的某个窗口吗？

实际上，$t$ 是窗口数值，而 $s_t$ 是序列中位置 $t$ 的值。这个值会在我们滑动到某个位置时被检查，但不是立即检查。

更准确地说：当窗口滑动到位置 $i$ 时，我们检查 $s_{t_i}$ 是否为 1，其中 $t_i$ 是窗口在位置 $i$ 时的数值。

但 $s_{t_i}$ 是序列的固定位置，而窗口在不断滑动。这建立了一个自指约束：窗口数值指向序列的某个位置，该位置的值必须是 1。

图论建模

状态机模型

定义状态为当前窗口的 $k$ 位二进制值，共 $2^k$ 个状态，记为 $0, 1, \dots, 2^k-1$。

序列 $s$ 对应一条长度为 $n$ 的状态路径：

• 初始窗口：前 $k$ 位 $s_0 \dots s_{k-1}$ 对应状态 $S_0$
• 第 $i$ 步：添加 $s_{i+k-1}$（如果是前 $k$ 步，则是构建初始窗口；之后是滑动）

约束：对于路径上的每个状态 $t$（即某个窗口的数值），要求 $s_t = 1$。

但 $s_t$ 不是当前状态，而是序列第 $t$ 位的值。这个值会在路径的某个位置出现：当窗口滑动到某个位置 $j$ 时，如果窗口数值等于 $t$，那么我们要求 $s_t = 1$。

而 $s_t$ 是序列的第 $t$ 位，它会影响以 $t$ 开头的窗口吗？不一定。

关键观察

设 $v$ 是一个 $k$ 位二进制数（状态）。如果 $v$ 作为窗口数值出现在路径中（即某个时刻窗口内容等于 $v$），那么根据条件，$s_v$ 必须是 1。

但 $s_v$ 是序列的第 $v$ 位，而 $v$ 是状态值。$s_v$ 会影响哪些窗口呢？

考虑位置 $v$：以 $v$ 开头的窗口内容是 $s_v s_{v+1} \dots s_{v+k-1}$，这个窗口的数值是某个 $w$。条件要求 $s_w = 1$。

所以这形成了一个链式约束。

建立约束图

定义一个有向图 $G$：

• 节点：$2^k$ 个状态（$k$ 位二进制数）
• 边：如果状态 $u$ 可以通过添加一个比特 $b$ 转移到状态 $v$，则存在边 $u \to v$，标记为 $b$

具体转移：$v = ((u \ll 1) \& \text{mask}) | b$

序列 $s$ 对应图上一条长度为 $n$ 的路径（从某个初始状态开始，经过 $n-1$ 次转移）。

约束：对于路径上的每个节点 $u$（即某个窗口数值），要求 $s_u = 1$。

但 $s_u$ 是什么？它是序列的第 $u$ 位的值，这个值由路径上的某条边决定。

更准确地说：路径的第 $u$ 步（从0开始计数）输出一个比特 $s_u$，这个比特是转移的标签。

所以约束变为：对于路径上的每个节点 $u$，要求在第 $u$ 步输出的比特是 1。

重新表述

我们有一条长度为 $n$ 的路径，路径上的每个位置 $i$ 有一个状态 $state_i$（窗口内容）和一个输出比特 $s_i$。

约束：对于每个位置 $i$，$s_{state_i} = 1$。

即：位置 $i$ 的状态值 $state_i$ 指向另一个位置 $j = state_i$，要求位置 $j$ 的输出比特为 1。

这是一个自指约束：每个位置的状态指向另一个位置，要求该位置的输出为 1。

动态规划算法

状态定义

由于 $k \leq 4$，$2^k \leq 16$，状态数很少。

我们可以在 DP 中记录当前路径的最后 $k$ 个比特（即当前状态），以及已经确定的输出比特中哪些位置必须是 1。

但约束涉及未来位置：当前状态 $u$ 要求位置 $u$ 的输出为 1。如果 $u$ 已经过去，我们检查是否满足；如果 $u$ 在未来，我们记录这个要求。

定义 DP 状态：

• 当前位置 $pos$（0 到 $n$）
• 当前窗口状态 $st$（$k$ 位二进制数）
• 一个集合 $mask$，表示哪些未来位置必须输出 1

但 $mask$ 可能很大（$n$ 可达 500），不能直接记录。

关键简化

由于 $k$ 很小，状态值 $u$ 的范围是 $[0, 2^k-1]$，即 $u < 16$。

因此，约束只涉及位置 0 到 15（如果 $k=4$）或更少。

所以，只有前 $2^k$ 个位置的约束是关键的。对于位置 $i \geq 2^k$，没有状态值会指向它（因为状态值最大为 $2^k-1$）。

重要结论：只有前 $2^k$ 个位置 $s_0, s_1, \dots, s_{2^k-1}$ 受到直接约束。其他位置 $s_i$（$i \geq 2^k$）没有状态指向它们，所以它们可以是 0 或 1 自由选择。

但等等：状态值 $u$ 指向位置 $u$，而 $u < 2^k$，所以确实只涉及前 $2^k$ 个位置。

因此，约束简化为：对于每个位置 $i$，如果 $state_i = j$，则 $s_j = 1$。

其中 $j < 2^k$。

新的理解

序列 $s$ 的前 $2^k$ 个比特是受约束的，后面的比特自由。

我们可以先确定前 $2^k$ 个比特，然后检查是否满足所有约束，最后乘以 $2^{n-2^k}$（后面每个位置自由选择 0 或 1）。

但约束是动态的：$state_i$ 依赖于序列的值。

建立自动机

由于 $k$ 很小，我们可以构建一个自动机，状态是当前窗口内容（$k$ 位），并且记录哪些位置已经满足了约束。

定义状态为 $(st, mask)$：

• $st$：当前窗口内容（$k$ 位）
• $mask$：一个 $2^k$ 位的位掩码，表示哪些位置已经确认为 1

初始状态：$(s_0 \dots s_{k-1}, 0)$

转移：添加一个比特 $b$：

• 新状态 $st' = ((st \ll 1) \& (2^k-1)) | b$
• 新掩码 $mask' = mask$
• 但我们需要添加约束：当前状态 $st$ 要求位置 $st$ 必须是 1。如果 $st$ 对应的比特在 $mask$ 中尚未设置，我们需要设置它，但前提是 $st$ 在当前路径中出现了。

实际上，约束是：如果状态 $st$ 出现在路径中，那么 $s_{st} = 1$。

在自动机中，当我们处于状态 $st$ 时，我们要求 $s_{st} = 1$。但 $s_{st}$ 是什么时候输出的？它是路径的第 $st$ 步的输出。

所以我们需要在自动机中记录：哪些位置已经输出了 1。

更精确的自动机

考虑构建序列的过程：我们逐步输出 $s_0, s_1, \dots, s_{n-1}$。

在输出 $s_i$ 时，当前窗口状态是基于最近的 $k$ 个输出。

我们需要确保：对于每个 $i$，如果存在某个 $j$ 使得 $state_j = i$，那么 $s_i = 1$。

等价地：对于每个 $i$，$s_i$ 必须为 1，除非没有状态等于 $i$。

因此，问题转化为：有多少个序列 $s$，使得集合 $\{i: s_i = 0\}$ 与所有状态值集合不相交？

最终算法

步骤1：枚举所有可能的状态值集合

由于 $k \leq 4$，状态值范围 $[0, 2^k-1]$ 最多 16 个值。

对于序列 $s$，设 $A = \{i: s_i = 1\}$ 是 1 的位置集合。

约束要求：所有出现在路径中的状态值都必须属于 $A$。

但哪些状态值会出现在路径中？这取决于序列 $s$ 本身，因为状态由连续的 $k$ 个比特决定。

步骤2：固定前 $2^k$ 个比特

由于状态值小于 $2^k$，只有前 $2^k$ 个位置可能被要求为 1。

我们可以枚举前 $2^k$ 个比特的所有可能（$2^{2^k}$ 种，最多 $2^{16}=65536$），对于每种枚举：

1. 检查是否自洽：对于每个位置 $i < 2^k$，如果 $s_i = 0$，那么是否可能没有状态等于 $i$？
2. 计算满足条件的序列总数（乘以 $2^{n-2^k}$）

但检查自洽性需要知道哪些状态会出现，这又依赖于序列。

步骤3：建立约束系统

定义变量 $x_i = s_i$（0 或 1），$i=0,\dots,n-1$。

约束：对于每个窗口起始位置 $i=0,\dots,n-k$： 设 $t_i = \text{bin}(x_i x_{i+1} \dots x_{i+k-1})$ 要求 $x_{t_i} = 1$

这是一个自指约束系统。

我们可以尝试直接求解这个约束系统。

步骤4：注意到 $k$ 很小，使用 DP

由于 $k \leq 4$，我们可以使用状态压缩 DP。

定义 $dp[pos][mask]$ 表示：

• 已经确定了前 $pos$ 个比特
• 当前窗口的最后 $k$ 个比特（即状态）为某个值，但我们需要记录更多

更好的定义： $dp[pos][st][req]$：

• $pos$：已经处理的位置数
• $st$：当前窗口状态（最近 $k$ 个比特）
• $req$：一个 $2^k$ 位的掩码，表示哪些位置已经被确认为必须为 1

转移：添加下一个比特 $b \in \{0,1\}$：

1. 新状态 $st' = ((st \ll 1) \& (2^k-1)) | b$
2. 新要求：当前状态 $st$ 要求位置 $st$ 为 1。所以如果 $st < pos$，我们已经知道 $x_{st}$ 的值，检查是否满足；如果 $st \geq pos$，记录这个要求。
3. 但 $req$ 掩码记录的是未来哪些位置必须为 1。

具体地：

• 当处于状态 $st$ 时，如果 $st < pos$，检查 $x_{st}$ 是否为 1
• 如果 $st \geq pos$，则要求 $x_{st} = 1$，设置 $req$ 中的对应位

最终，在 $pos=n$ 时，检查所有要求是否满足（$req$ 中要求为 1 的位置，对应的 $x$ 值是否为 1）。

步骤5：简化 DP

由于 $k$ 很小，我们可以将 $st$ 和部分历史信息编码。

实际上，我们只需要知道最近 $k$ 个比特，因为窗口只依赖这些。

DP 状态：$(pos, st, req)$

• $pos$：0 到 $n$
• $st$：$k$ 位状态，$0 \leq st < 2^k$
• $req$：$2^k$ 位掩码，表示哪些位置必须为 1

转移：对于 $b=0,1$：

1. $st' = ((st \ll 1) \& (2^k-1)) | b$
2. 检查约束：状态 $st$ 要求 $x_{st} = 1$
   • 如果 $st < pos$，已经确定了 $x_{st}$，检查是否满足
   • 如果 $st \geq pos$，在 $req$ 中标记位置 $st$ 必须为 1
3. 但 $x_{st}$ 的值是什么？对于 $st < pos$，我们需要知道之前选择的 $x_{st}$。这没有记录在状态中！

因此，我们需要记录历史选择的比特。

步骤6：记录必要历史

由于 $st < 2^k$，我们只需要知道前 $2^k$ 个比特的值。

所以我们可以将前 $2^k$ 个比特的选择作为状态的一部分。

定义状态：$(pos, st, prefix)$，其中 $prefix$ 是前 $2^k$ 个比特的选择（$2^k$ 位掩码）。

但 $pos$ 可能大于 $2^k$，此时 $prefix$ 已经固定。

对于 $pos \geq 2^k$，$prefix$ 不再变化。

转移：

• 如果 $pos < 2^k$：选择 $x_{pos} = b$，更新 $prefix$
• 检查约束：状态 $st$ 要求 $x_{st} = 1$，从 $prefix$ 中检查（如果 $st < pos$）或记录要求

但记录要求需要另一个掩码。

最终可行算法

由于 $k \leq 4$，$2^k \leq 16$，我们可以暴力枚举前 $2^k$ 个比特的所有可能（最多 65536 种）。

对于每种前 $2^k$ 个比特的赋值，检查是否满足所有约束：

• 对于每个窗口位置 $i=0,\dots,2^k-k$（因为 $n \geq 2^k$，且只需要检查到 $2^k-k$ 就能覆盖所有可能指向前 $2^k$ 个位置的约束）
• 计算 $t_i = \text{bin}(x_i \dots x_{i+k-1})$
• 检查 $x_{t_i}$ 是否为 1

如果满足，那么这种赋值是可行的。对于后面的 $n-2^k$ 个比特，可以自由选择 0 或 1，贡献 $2^{n-2^k}$。

因此，答案 = (满足条件的前 $2^k$ 比特赋值数) × $2^{n-2^k}$。

但需要验证：对于 $i > 2^k-k$ 的窗口，$t_i$ 可能 $\geq 2^k$，此时约束 $x_{t_i}=1$ 自动满足（因为 $t_i \geq 2^k$ 的位置可以自由选择为 1）。

实际上，对于 $i \geq 2^k-k+1$，窗口包含位置 $\geq 2^k$，这些位置的值是自由的。但 $t_i$ 可能仍然 $< 2^k$。

例如，$k=2$，序列长度 $n=4$，$2^k=4$。窗口位置 $i=2$：$x_2 x_3$，如果 $x_2=0, x_3=1$，则 $t=1$，要求 $x_1=1$。这仍然涉及前 4 个位置。

所以我们需要检查所有窗口，直到 $i = n-k$。

因此，算法为：

1. 枚举前 $2^k$ 个比特的所有赋值（$2^{2^k}$ 种）
2. 对于每种赋值，检查所有窗口 $i=0,\dots,\min(2^k-k, n-k)$ 的约束
   • 实际上需要检查 $i=0,\dots,n-k$，但后面的窗口可能涉及自由位
3. 如果所有约束满足，贡献 $2^{\max(0, n-2^k)}$

复杂度：$O(2^{2^k} \cdot n)$，对于 $k=4$，$2^{16}=65536$，$n=500$，$65536×500=3.3×10^7$，可接受。

验证样例

$n=4, k=2$，$2^k=4$

枚举前 4 个比特 $x_0 x_1 x_2 x_3$：

窗口：

• $i=0$：$x_0 x_1 = t_0$，要求 $x_{t_0}=1$
• $i=1$：$x_1 x_2 = t_1$，要求 $x_{t_1}=1$
• $i=2$：$x_2 x_3 = t_2$，要求 $x_{t_2}=1$

检查所有 $2^4=16$ 种赋值：

• $0111$：$t_0=1$，$x_1=1$ ✓；$t_1=3$，$x_3=1$ ✓；$t_2=3$，$x_3=1$ ✓
• $1111$：同样满足

其他都不满足。所以 2 种。

后面 $n-2^k=0$ 个自由位，贡献 $2^0=1$。

总方案数 2，与样例一致。

总结

最终算法：

1. 枚举前 $2^k$ 个比特的所有可能赋值
2. 对于每种赋值，检查所有窗口约束
3. 统计满足条件的赋值数 $cnt$
4. 答案 = $cnt \times 2^{\max(0, n-2^k)} \mod 998244353$

由于 $k \leq 4$，$2^k \leq 16$，枚举 $2^{16}=65536$ 种情况可行。