ABC194 F - Digits Paradise in Hexadecimal (600)
最初の考察
桁DPだと何か難しそう
これまでに使った数字を保持しておいてi桁目以降でj個の数字からk個の相違なる数を作ることができるパターンを求める
何か計算が合わず駄目
最終的な考察
$ dp[i][j][k] でi桁目まで見て元の数より小さいかどうか、k種類の数字を使った場合の数とする
$ k = 0の場合、頭から0しか使っていない状態を指す
初期状態は、
$ dp[0][1][0] = 1
$ dp[0][1][0] = a_0 - 1
$ dp[0][0][1] = 1
元々の数字で使われている数の集合を桁ごとに更新していく
$ dp[i][1][j] の更新元は以下の3種類
$ dp[i-1][1][j] \times j
既に使われている数字を選んだ場合
$ dp[i-1][1][j-1] \times \min(15, 16-(j-1))
まだ使われていない数字を選んだ場合
0以上$ a_i 未満以下の数$ l について $ dp[i-1][0][j] または$ dp[i-1][0][j-1]
$ lが既に使われている場合、数の種類は増えないので前者
まだ使われていない場合、数の種類が増えるので後者
最後の桁まで見てk種類になっている部分の値を全て足したのが答え
各桁ごとに最大$ 16^2のループが回るので全体で$ O(\log N)