コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2197 (記事作成時点)

供養

解法

$N$ を最上位の桁が0でない $L$ 桁の $d(=16)$ 進数とする
$\mathit{DP}_{l, k}$ を以下の条件を満たす $d$ 進数 $H_{l}$ のパターン数とする
- 上位の0埋めを許容してちょうど $l$ 桁で表現できる
- 0埋めの0を除き、使用している記号がちょうど $k$ 種類
- $N$ の上位 $l$ 桁で表現される数を $N_{l}$ としたとき、$0 \lt H_{l} \lt N_{l}$ である
$1 \le l \lt L$ について、$0 \lt H_{l} \lt N_{l}$ である $H_{l}$ については末尾に任意の記号を追加しても $0 \lt H_{l + 1} \lt N_{l + 1}$ となるので、以下の計算ができる
- $l + 1$ 桁目を既に使用している $k$ 種類の記号から選ぶ場合について、$\mathit{DP}_{l + 1, k}$ に $\mathit{DP}_{l, k} \times k$ を加算する
- $l + 1$ 桁目に未使用の記号を選ぶ場合について、$\mathit{DP}_{l + 1, k + 1}$ に $\mathit{DP}_{l, k} \times (d - k)$ を加算する
$1 \le l \lt L$ について、$\mathit{DP}_{l, k}$ でカウントされる $H_{l}$ から生成されない、$\mathit{DP}_{l + 1, k}$ でカウントされる $H_{l+ 1}$ は以下がある
- 上位 $l$ 桁が $0$ で、最下位の桁が $0$ 以外
  - $\mathit{DP}_{l + 1, 1}$ に $d - 1$ を加算する
- 上位 $l$ 桁で表現される数が $N_{l}$ で、最下位の桁が $N$ の上位 $l + 1$ 桁目の記号 $n_{l + 1}$ 未満
  - $N_{l}$ で使用している記号の集合を $S_{l}$ とする
  - $0 \le h \lt n_{l + 1}$ について、$h \in S_{l}$ ならば $\mathit{DP}_{l + 1, |S_{l}|}$ を $1$ 加算し、$h \notin S_{l}$ ならば $\mathit{DP}_{l + 1, |S_{l}| + 1}$ を $1$ 加算する
$N$ と同値でも問題の条件を満たすので、最後に $\mathit{DP}_{L, |S_{L}|}$ を $1$ 加算する
$\mathit{DP}_{L, K}$ が答えとなる