BZOJ 1009 – 「HNOI2008」GT考试

题目链接:BZOJ 1009

设准考证号为目标串$S$,不吉利的数字串为模式串$T$。

考虑对$S$和$T$进行模式匹配,$f(i,j)$表示匹配到目标串的第$i$位和模式串的第$j$位,并且之前没有出现过完全匹配的子串,这种情况下目标串前$i$位的组成方案数量。那么显然答案为$\sum_{i=0}^{m-1} f(n, i)$。

这时候有两种情况:

  • $s_i = t_j$,$f(i, j) = f(i – 1, j – 1)$
  • $s_i \neq t_j$, $f(i, j) = \sum f(i – 1,k)[{\rm fail}(k) = j – 1]$

所以$f(i,j)$要么从$f(i-1,j-1)$转移,要么从能跳转到$f(i-1,j-1)$的$f(i-1,k)$转移(基于$j-1$结尾的后缀和$i-1$为结尾的后缀已经匹配完了)。

考虑$n \leq 10^9$,这个式子要继续化简。我们设一个新的函数$g(u, v)$,表示在$u$位置的所有可能取值中,$u$能转移到$v$的方案数,显然$g(u,v)$由两部分构成:一个是$v=u + 1$并且$v$匹配成功,另一个是${\rm fail}(v) = u – 1$。那么我们可以得到:

$$f(i, j) = \sum_{k=0}^{m-1} f(i – 1, k) \times g(k, j)$$

$k$的范围$[0,m-1]$表示合法串中不能由完整的模式串匹配,求和部分就是统计转移的贡献。

此时我们可以把上式转化为

$$ \begin{aligned} & \begin{bmatrix} f(i-1, 0) & f(i-1,1) & \cdots & f(i-1, m-1) \\ f(i-1, 0) & f(i-1,1) & \cdots & f(i-1, m-1) \\ \vdots & \vdots & \ddots & \vdots \\ f(i-1, 0) & f(i-1,1) & \cdots & f(i-1, m-1)    \end{bmatrix} \cdot g \\ = & \begin{bmatrix} f(i, 0) & f(i,1) & \cdots & f(i, m-1) \\ f(i, 0) & f(i,1) & \cdots & f(i, m-1) \\ \vdots & \vdots & \ddots & \vdots \\ f(i, 0) & f(i,1) & \cdots & f(i, m-1)    \end{bmatrix} \end{aligned}   $$

因此可以使用矩阵快速幂进行优化,渐进时间复杂度$O(m^3 \log n)$。

 

说点什么

avatar
50
  Subscribe  
提醒