「子序列计数」题解

题意简化

给定字符串 $s$，字符集大小为 $9$，多次询问区间 $[l, r]$ 内本质不同子序列的数量（不含空序列）。
$n, q \le 10^5$。

核心观察

1. 经典DP公式

设 $dp[i]$ 表示前 $i$ 个字符的本质不同子序列数（包含空序列）。
转移：

$$dp[i] = 2 \times dp[i-1] - dp[\text{last}[s[i]] - 1] $$

其中 $\text{last}[c]$ 是字符 $c$ 上一次出现的位置。

解释：

• $2\times dp[i-1]$：每个旧子序列可以选择是否加上 $s[i]$
• 减去 $dp[\text{last}-1]$：减去上次出现时已经计算过的重复子序列

最终答案（不含空序列）为 $dp[n]-1$。

2. 区间查询问题

我们需要对任意区间 $[l, r]$ 计算答案。

设 $f(l, r)$ 表示 $s[l..r]$ 的子序列数（包含空序列）。
从 $l$ 开始做同样的 DP，但 $\text{last}[c]$ 需要基于区间 $[l, r]$ 重新计算。

关键思路：矩阵乘法 + 前缀积

1. 矩阵表示

考虑字符集大小 $m=9$。
将 DP 过程用矩阵表示，状态向量包含 $m+1$ 个值：
$[dp, cnt_1, cnt_2, \dots, cnt_m]$，其中 $cnt_c$ 表示以字符 $c$ 结尾的子序列数。

处理字符 $c$ 时：

1. 新的 $dp = 2\times dp_{old} - cnt_c$
2. 新的 $cnt_c = dp_{old}$
3. 其他 $cnt_{c'}$ 不变

对应一个 $(m+1)\times(m+1)$ 的转移矩阵 $M_c$。

2. 区间查询转化为矩阵乘法

对于区间 $[l, r]$：

$$\text{答案向量} = \text{初始向量} \times M_{s[l]} \times M_{s[l+1]} \times \dots \times M_{s[r]} $$

初始向量为 $[1, 0, 0, \dots, 0]$（只有空序列）。

3. 快速查询

预处理前缀矩阵积：
$P_i = M_1 \times M_2 \times \dots \times M_i$

则区间 $[l, r]$ 的矩阵积为：

$$P_{l-1}^{-1} \times P_r$$

由于 $m=9$，矩阵只有 $10\times10$，求逆和乘法都是 $O(1)$。

算法步骤

1. 预处理转移矩阵

   • 对每个字符 $c$，构造对应的 $M_c$
   • 计算前缀积 $P_i = P_{i-1} \times M_{s[i]}$
   • 同时计算前缀积的逆 $P_i^{-1}$

2. 回答查询 对每个询问 $[l, r]$：

   • 计算 $Q = P_{l-1}^{-1} \times P_r$
   • 初始向量 $V_0 = [1, 0, \dots, 0]$
   • $V = V_0 \times Q$
   • 答案 = $V[0] - 1$（去掉空序列）

复杂度

• 预处理：$O(n \times m^3)$，但 $m=9$，实际 $O(n)$
• 每次查询：$O(m^3) = O(1)$
• 总复杂度：$O(n + q)$，可过 $10^5$

关键点

• 将 DP 转化为矩阵乘法
• 利用前缀积和逆矩阵快速回答区间查询
• 字符集小（$m=9$）是核心，矩阵操作是常数时间