[LOJ6074 2017 山东一轮集训 Day6]子序列

对于一个区间考虑如何dp。

在每一个位置钦定转移到某种字符上,并且走到最近的这种字符,相当于建出了一个DAG,可以统计本质不同的子序列。

设 \(f_{i,j}\) 表示在第 \(i\) 位上,钦定转移到字符 \(j\) 的方案数,那么从 \(i\) 到 \(i+1\) 时,仅有 \(f_{i+1,s_i}\) 与 \(f_i\) 不同。

因为根据定义,只有 \(s_i\) 的转移发生了变化。

而且转移可以写成矩阵的形式,转移矩阵只有 \(s_i\) 这一行和对角线是 \(1\),并且可以得到它的逆矩阵。

那么预处理转移矩阵前缀积和逆矩阵前缀积即可。

但是这样复杂度有点高,矩阵有特殊性质,一次转移相当于把 \(s_i\) 这一行变成之前所有行的和。逆矩阵类似。

那么矩乘的复杂度就只有 \(n^2\) 了,实际上只需要额外维护一个矩阵每一列的和,就可以做到 \(O(n)\) 的矩乘。

复杂度 \(O(10n+10q)\)。


在《[LOJ6074 2017 山东一轮集训 Day6]子序列》上留下第一个评论