标签：frac 题解 sum times 序列 CF1920E

CF1920E

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

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

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

\[(x+1)(y+1) \]

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

\[f_{i,j}=\sum f_{i-p\times j,p} \]

\(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\}]\)，即：

\[f_{i,j}=\sum\limits_{p=1}^{\min\{\frac{i}{j},k+1-j\}} f_{i-p\times j,p} \]

code

标签：frac,题解,sum,times,序列,CF1920E
From： https://www.cnblogs.com/wang-holmes/p/17979739