题解

思路

把字符串写成若干个 1 及其间的零段。令 $a_i$ 为第 $i$ 个 1 左侧零段长度加一，并在最后加入尾零段长度加一。每个 1 对好子串数的贡献是相邻两项之积，因此总数为 $\sum a_i a_{i+1}$。包含该 1 的最长好子串长度是 $a_i+a_{i+1}-1$。

做法

问题等价于统计正整数序列，使相邻乘积和为 $n$，且每对相邻数满足 $a_i+a_{i+1}-1\le k$。

令 $dp[s][x]$ 表示当前相邻乘积和为 $s$、最后一项为 $x$ 的序列数。空贡献时任意首项 $x\in[1,k]$ 都有一个初始方案。枚举下一项 $y$，若 $x+y-1\le k$，则转移到 $s+xy$。最终对 $dp[n][x]$ 求和。

当 $k=1$ 时所有相邻项只能为一，对应唯一字符串 1 重复 $n$ 次。小规模可以枚举长度不超过 $n$ 的全部二进制串并直接检查。

复杂度

时间复杂度 $O(nk\log n)$，空间复杂度 $O(nk)$。