题解

思路

对“不能最终全亮”的串按最外层阻塞结构做唯一分解。记 $f_i$ 为长度 $i$ 的计分串数，辅助数组 $g_i$ 统计可接在阻塞结构右侧的前缀，$h_i=\sum_{j=1}^{i-1}f_jf_{i-j}$ 表示两个计分块的拼接数。可以得到

所有运算直接对给定的任意模数进行，不使用逆元。

做法

子任务 1

枚举全部 $2^n$ 个串，反复应用任意当前合法的传播操作直到闭包稳定，统计能变成全 $1$ 的串。复杂度 $O(2^n n^3)$。

子任务 2

直接使用分解递推，但每次需要 $h_j$ 时重新枚举断点计算卷积，复杂度 $O(n^3)$、空间 $O(n)$。

子任务 3

按长度递增时预先缓存每个 $h_i$，每对 $(j,i-j)$ 只贡献一次。于是所有 $g,f,h$ 转移总计 $O(n^2)$，空间 $O(n)$。

复杂度

三层算法时间复杂度分别为 $O(2^n n^3)$、$O(n^3)$、$O(n^2)$，空间复杂度分别为 $O(1)$、$O(n)$、$O(n)$。

正确性

逐串枚举按定义求出传播闭包。分解 DP 将每个非计分串按第一个无法跨越的阻塞结构唯一归入一个 $h_jg_{i-2j-1}$ 项，因此用全部首尾为 $1$ 的候选数减去这些互不重叠的坏串，恰得 $f_i$。缓存 $h_i$ 只复用同一卷积值，不改变递推。