P12087 [RMI 2019] 好数 / Lucky Numbers

线段树矩乘维护数位 DP。

令

dp_{i,0/1,0/1}

表示当前第

i

位，是否顶到上界，第

i

位是否为

1

的方案数量，

x_i

为

x

从高到低第

i

位。

则有：

$dp_{i,0,0}=\begin{cases}9dp_{i-1,0,0}+8dp_{i-1,0,1}+(x_i-1)dp_{i-1,1,0}+(x_i-2)dp_{i-1,1,1}&x_i>3\\9dp_{i-1,0,0}+8dp_{i-1,0,1}+(x_i-1)dp_{i-1,1,0}+(x_i-1)dp_{i-1,1,1}&2\le x_i\le 3\\9dp_{i-1,0,0}+8dp_{i-1,0,1}+x_idp_{i-1,1,0}+x_idp_{i-1,1,1}&0\le x_i\le 1\end{cases}$ $d p_{i, 0, 0} = ⎩ ⎨ ⎧ 9 d p_{i - 1, 0, 0} + 8 d p_{i - 1, 0, 1} + (x_{i} - 1) d p_{i - 1, 1, 0} + (x_{i} - 2) d p_{i - 1, 1, 1} 9 d p_{i - 1, 0, 0} + 8 d p_{i - 1, 0, 1} + (x_{i} - 1) d p_{i - 1, 1, 0} + (x_{i} - 1) d p_{i - 1, 1, 1} 9 d p_{i - 1, 0, 0} + 8 d p_{i - 1, 0, 1} + x_{i} d p_{i - 1, 1, 0} + x_{i} d p_{i - 1, 1, 1} x_{i} > 3 2 \leq x_{i} \leq 3 0 \leq x_{i} \leq 1$
- 前面的系数 $9$ 表示第 $i$ 位不能选 $1$ ， $8$ 表示不能选 $1$ 或 $3$ ，后面的系数 $x_i-1$ 和 $x_i-2$ 同理。
$dp_{i,0,1}=dp_{i-1,0,0}+dp_{i-1,0,1}+[x_i>1]\left(dp_{i-1,1,0}+dp_{i-1,1,1}\right)$ 。
$dp_{i,1,0}=\begin{cases}dp_{i-1,1,0}+[x_i\ne 3]dp_{i-1,1,1}&x_i\ne 1\\0&x_i=1\end{cases}$ 。
$dp_{i,1,1}=\begin{cases}dp_{i-1,1,0}+dp_{i-1,1,1}&x_i=1\\0&x_i\ne1\end{cases}$ 。
$dp_{0,1,0}=1$ 。

这个显然可以矩阵乘法维护。

令

f=\begin{pmatrix}dp_{i-1,0,0}&dp_{i-1,0,1}&dp_{i-1,1,0}&dp_{i-1,1,1}\end{pmatrix}

，对于

x_i>3

，可以得出转移矩阵为：

\begin{pmatrix}9&1&0&0\\8&1&0&0\\x_i-1&1&1&0\\x_i-2&1&1&0\end{pmatrix}

x_i\le 3

的部分转移矩阵构造类似。

直接线段树维护即可。

文章操作