CF1920E

被这种题卡了，脸都不要了。

仔细读题，发现序列可以分成两部分（$0$ 和 $1$）来考虑。

在合法序列中，对于一个 $1$，它产生的子串贡献一定是（假设与上一个 $1$ 之间有 $x$ 个 $0$，与下一个 $1$ 之间有 $y$ 个 $0$）：

如果去 DP 这 $n$ 个 $1$，易得转移方程：

$f_{i,j}$ 表示：当前贡献了 $i$ 个合法子串，上一个 $1$ 到现在的 $1$ 的长度为 $j$ 的组成序列方案数。

接下来考虑 $p$ 的值域。

要使式子成立，有：$p\in [1, \frac{i}{j}]$。

考虑题目限制（最长合法串长度不大于 $k$），有：$p\in [1,k+1-j]$。

所以 $p\in [1,\min{\frac{i}{j},k+1-j}]$，即：

code