题解：P13382 [GCJ 2011 Finals] Runs

· · 题解

什么出题人搬这个题到模拟赛里还把段数 \bm{\le100} 写掉了啊？

考虑 DP 状态，设 f_{i,j} 表示考虑前 i 种字符，形成了 j 个颜色段的方案数，初始值为 f_{1,1}=1。

考虑如何转移，设当前有 j 段，总长度为 \text{len}，将第 i+1 种颜色分成 k 段，插入到当前形成的序列里，有 \dbinom{\text{cnt}_{i+1}-1}{k-1} 种划分方案；在这 k 段中，选择前 l 段插入到某段的内部，这样的间隙共有 \text{len}-j 个，会额外产生 l 个新的连续段；剩余 k-l 段插入到段之间，这样的间隙有 j+1 个，故有：

f_{i+1,j+k+l}\overset{+}\leftarrow f_{i,j}\cdot\dbinom{\text{cnt}_{i+1}-1}{k-1}\dbinom{\text{len}-j}{l}\dbinom{j+1}{k-l}

时间复杂度为 \mathcal O(|\Sigma|m^3)，注意循环的上下界。

虽然这样就能过了，但显然有特别大的优化空间。

考虑使用容斥，设 f_{i,j} 为考虑前 i 种字符，至多有 j 个分段点的方案数，这意味着到最后可能会有一些多余的分段点，初始值为 f_{0,0}=1，有转移：

f_{i,j}=\sum_{k=1}^{\min(\text{cnt}_i,j)}f_{i-1,j-k}\cdot\dbinom{\text{cnt}_i-1}{k-1}\dbinom{j}{k}

设共有 m 个分段点，答案为：

\fbox{answer}=\sum_{i=1}^m(-1)^{m-i}\dbinom{n-i}{m-i}f_{26,i}

时间复杂度为 \mathcal O(|\Sigma|m^2)。

然后你发现这个是卷积的形式：

f_{i,j}=(\text{cnt}_i-1)!j!\sum_{k=1}^{\min(\text{cnt}_i,j)}\dfrac{1}{k!(k-1)!(\text{cnt}_i-k)!}\cdot\dfrac{f_{i-1,j-k}}{(j-k)!}

使用 NTT 就能做到 \mathcal O(|\Sigma|m\log m) 甚至 \mathcal O(m\log m\log|\Sigma|)，然鹅这个题模数不友善。