[题解]CF1327F

标签：CF1327F 题解 lst 端点 Theta mathrm

首先拆位，然后考虑限制会带来什么。
要求与起来是 \(1\) 的必须全是 \(1\)，差分打个标记。
要求与起来是 \(0\) 的必须至少有一个 \(0\)，考虑如何计数。
计数问题有可能是动态规划，我们发现需要考虑的只有最后一个 \(0\) 的位置，所以设 \(f_{i,j}\) 表示填好前 \(i\) 个数、最后一个 \(0\) 在 \(j\) 的方案数。
但这样还不方便转移，我们应该预处理一个 \(\mathrm{lst}_{i}\) 表示 \(i\) 填 \(1\) 时最后一个 \(0\) 最左填到哪，这个可以用左端点更新右端点。
那么此时有下式：

\[f_{i,j}=\begin{cases} 0,\ &j<\mathrm{lst}_i\\ f_{i-1,j},\ &\mathrm{lst}_i\le j<i\\ \sum_{x=\mathrm{lst}_{i-1}}^{i-1}f_{i-1,x},\ &j=i \end{cases} \]

这个式子的意义比较显然，上式表示不合法，中式表示 \(i\) 只能填 \(1\)，下式表示只要满足 \(i-1\) 的条件就随便填。
然后注意到 \(\mathrm{lst}\) 不降，所以双指针维护一个区间和，\(i\) 也可以滚掉。
最后每一位乘起来就是答案。

时间 \(\Theta(nk)\)，空间 \(\Theta(n)\)。

标签：CF1327F,题解,lst,端点,Theta,mathrm
From： https://www.cnblogs.com/juruoajh/p/16852088.html