https://atcoder.jp/contests/abc194/tasks/abc194_f
前提知識
解説
https://atcoder.jp/contests/abc194/submissions/20736872
この問題は桁DPで解く。
なお、桁DPが初見という人は他のオーソドックスな問題を先に解くことをお勧めする。
桁DP
以下のような定義で解く。
dp[digit][kind][isless][leadingzero]
digit桁目まで数字が確定していて、
既にkind種類の数字を使用していて、
Nよりもすでに小さいかの状態がislessで、
これまで選択した数がすべて0であるかの状態がleadingzeroである
数字の組み合わせ
他の人の解法を見ていると定義に失敗した感じが否めないが、これを丁寧に丁寧に実装すると通る。
遷移については、説明がややこしいので、実装にコメントした。
遷移後にちゃんとDPの状態を崩さないように丁寧に丁寧に実装する。
なお、leadingzero=1のとき、leading-zeroは種類数にはカウントしないので、kind=0を維持すること。
DPはある条件をkeyにすることでまとめることのできる状態をまとめて、抽象化した状態を最小化したらうまくいくみたいな問題なのだが、
抽象化が足らないとこんなことになる。特に桁DPは。
（逆に言えば、抽象化が甘くても何とかなるのが桁DPともいえるが）
string N; int K; map<char, int> dic; mint dp[201010][18][2][2]; // dp[digit][kind][isless][leadingzero] //--------------------------------------------------------------------------------------------------- mint solve() { bitset<16> used; int len = N.length(); dp[0][0][0][1] = 1; rep(digit, 0, len) { int x = dic[N[digit]]; rep(kind, 0, 17) rep(isless, 0, 2) rep(leadingzero, 0, 2) { mint& cur = dp[digit][kind][isless][leadingzero]; if (isless) { // 既にNより小さい場合において、既に選択された数字を選ぶ場合の遷移 dp[digit + 1][kind][isless][leadingzero] += cur * kind; if (!leadingzero) { // 既にNより小さい場合、かつ、leadingzeroじゃない場合において、新しい数を選ぶ場合 dp[digit + 1][kind + 1][isless][leadingzero] += cur * (16 - kind); } else { // leadingzeroの場合は種類数をカウントしない（leadingzeroは種類にカウントしない）ためkind=0であるはず // 既にNより小さい場合、かつ、leadingzeroである場合において、0を選択する場合（leadingzeroを継続する場合） dp[digit + 1][kind][isless][1] += cur; // 既にNより小さい場合、かつ、leadingzeroである場合において、0以外を選択する場合 dp[digit + 1][kind + 1][isless][0] += cur * (16 - kind - 1); } } else { // まだNより小さくない（Nと等しい）場合は、小さくなるように数を選択する rep(nxt, 0, x) { // 先頭で0を選ぶ場合のみleading-zeroになるので、そちらに遷移をさせる if (digit == 0 && nxt == 0) dp[digit + 1][0][1][1] += cur; else { // それ以外の場合は、種類数が増えるかを確認して、遷移を行う bitset<16> used2 = used; used2.set(nxt); dp[digit + 1][used2.count()][1][0] += cur; } } } } // こちらの遷移は先頭digit桁がNと同じになるように遷移させるもの int pre = used.count(); used.set(x); int post = used.count(); if (digit == 0) dp[digit + 1][post][0][0] += dp[digit][pre][0][1]; else dp[digit + 1][post][0][0] += dp[digit][pre][0][0]; } mint ans = dp[len][K][0][0]; // Nと全く同じパターン。K種類であればここで計算される ans += dp[len][K][1][0]; // N未満でK種類のもの return ans; } //--------------------------------------------------------------------------------------------------- void _main() { rep(i, 0, 10) dic[char('0' + i)] = i; rep(i, 0, 6) dic[char('A' + i)] = 10 + i; cin >> N >> K; cout << solve() << endl; }