https://atcoder.jp/contests/abc194/tasks/abc194_f

前提知識

桁DP

解説

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;
}

はまやんはまやんはまやん

hamayanhamayan's blog

Digits Paradise in Hexadecimal [AtCoder Beginner Contest 194 F]

前提知識

解説

桁DP