結果

問題 No.2772 Appearing Even Times
ユーザー InTheBloomInTheBloom
提出日時 2024-07-18 16:15:36
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 935 bytes
コンパイル時間 5,430 ms
コンパイル使用メモリ 171,964 KB
実行使用メモリ 89,652 KB
最終ジャッジ日時 2024-07-18 16:15:47
合計ジャッジ時間 11,201 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 17 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 3 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    string n = readln.chomp;
    auto N = new int[](n.length);
    foreach (i, c; n) N[i] = c - '0';

    solve(N);
}

void solve (int[] N) {
    const long MOD = 998244353;

    const int len = N.length.to!int;

    long[Tuple!(int, int, bool, bool)] memo;
    long dp (int i, int set, bool has, bool less) {
        auto key = tuple(i, set, has, less);
        if (key in memo) return memo[key];
        if (i == len) {
            if (has && set == 0) return 1;
            return 0;
        }

        long res = 0;
        foreach (nex; 0..10) {
            if (!less && N[i] < nex) continue;

            int st = set;
            if (has || 0 < nex) st ^= (1 << nex);
            bool h = has || 0 < nex;
            bool l = less || nex < N[i];

            res += dp(i + 1, st, h, l);
            res %= MOD;
        }

        return memo[key] = res;
    }

    writeln(dp(0, 0, false, false));
}
0