P12087 [RMI 2019] 好数 / Lucky Numbers

Nygglatho · 2025-11-14 13:40:54 · 题解

线段树矩乘维护数位 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}
  • 前面的系数 9 表示第 i 位不能选 1，8 表示不能选 1 或 3，后面的系数 x_i-1 和 x_i-2 同理。

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

令 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，可以得出转移矩阵为：