CF1152F2 Neko Rules the Catniverse (Large Version) 题解

发现挨位考虑填哪个不太现实，考虑值域。

令 \(dp_{i,j,st}\) 表示考虑到 \(i\)，此时序列长度为 \(j\)，\(i-m\) 到 \(i-1\) 填空状态为 \(st\) 的方案数，考虑选/不选数即可：

\(dp_{i,j,st}\times (\text{popcount}(st)+1)\to dp_{i+1,j+1,(2st+1)\&2^m},dp_{i+1,j,(2st)\&2^m}\)

乘上那个 \(\text{popcount}(st)+1\) 是因为 \(i\) 只能放到 \(a_k=[i-m,i-1]\) 位置 \(k\) 的后面或者开头。

然后发现 \(O(n2^mk)\) 不太行，但是 \(2^m\times k\) 非常小，想到矩阵优化。

复杂度 \(O((2^mk)^3\log n)\) 即可。