例一

luogu P3193 [HNOI2008]GT考试

思路

容易想到是数位dp, 设 $dp[i]$ 是准考证号到第 $i$ 位的方案数

错误思路: $dp[i] = dp[i-1]*(当前位可选方案数)-(选了第i位重复的方案)$

简单的想重复的方案就是最后一段是不吉利数字,就有 $dp[i-m]$

但就如样例所示的不吉利数字如果是 111

在 $dp[i-1]$ 已经排除了 $i-1$ 位是 1, $i-2$ 位是 1 的情况

转移 $dp[i]$ 要在 $dp[i-1]$ 的基础上做排除, 就会重复排除 $i-1$ 位是 1, $i-2$ 位是 1 的情况

所以这时候就要考虑 KMP

设 $dp[i][j]$ 是到第 $i$ 位准考证, 正在匹配不吉利数字的第 $j$ 位 时候的方案数

对于下一位加进来的数字,就可以根据 KMP 转移 $j$

  • 如果匹配 $dp[i][j] -> dp[i+1][j+1]$
  • 如果不匹配 $dp[i][j] -> dp[i+1][用KMP匹配找到某next?]$

最后答案要求不能完全匹配不吉利数字

设不吉利数组是 $[0, m)$ 那么 $j == m$ 就是全匹配了

$res=\sum\limits_{i=0}^{m-1}dp[n][i]$

因为 $n$ 很大，所以考虑 矩阵快速幂

预处理出一个数组

$g[i][k]$ 表示从不吉利数字匹配到 $i$ 位转移到第 $k$ 位的方案

对于不吉利数字每一位 $i$ 枚举新加入的数字 $0 -9$ 用KMP匹配出 $k$

此时状态转移方程为 $dp[i][j] = \sum\limits_{k=0}^{m-1}dp[i-1][k]\times g[k][j]$

构造矩阵

$$
\begin{bmatrix}
f[i][0] & f[i][1] & \cdots & f[i][m]
\end{bmatrix}
\times
\begin{bmatrix}
g[0][0] & g[0][1] & \cdots & g[0][m] \\
g[1][0] & g[1][1] & \cdots & g[1][m] \\
\vdots & \vdots & \ddots & \vdots \\
g[m][0] & g[m][1] & \cdots & g[m][m]
\end{bmatrix}
=
\begin{bmatrix}
f[i+1][0] & f[i+1][1] & \cdots & f[i+1][m]
\end{bmatrix}
$$

$F_0\times G^n=F_n$

初始状态 $f[0][0]=1$

$F_n[\cdots]=G^n[0][\cdots]$

代码

例二

leetcode P3193 [HNOI2008]GT考试

思路

这题与上题不同的地方主要就是有上限下限限制

一般的解决技巧就是 [0, 上限] - [0, 下限)

转化成只有上限

设 $dp[i][j][k]$ 是枚举到第 $i$ 位正在匹配 $evil[j]$ , $k$ 表示是否达到上限

因为对每一位的字母有要求,所以我们修改一下 $g$ 数组

令 $g[i][j]$ 表示匹配 $evil[i]$ 时新加的字母是 $j$ 转移到的下标

$dp$ 状态转移应该就是经典的数位dp转移 (其实是懒得写了)

tips: 因为难以得到 下限-1, 所以用 [0, 上限]-[0, 下限]+(下限是好字符串就减多了)

代码

赏