結果

問題 No.2772 Appearing Even Times
ユーザー InTheBloomInTheBloom
提出日時 2024-07-18 16:18:31
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 1,687 ms / 4,000 ms
コード長 1,248 bytes
コンパイル時間 5,085 ms
コンパイル使用メモリ 170,480 KB
実行使用メモリ 324,104 KB
最終ジャッジ日時 2024-07-18 16:18:57
合計ジャッジ時間 25,351 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1,687 ms
324,104 KB
testcase_09 AC 1,612 ms
323,968 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1,560 ms
323,584 KB
testcase_13 AC 1,545 ms
321,820 KB
testcase_14 AC 1,578 ms
323,032 KB
testcase_15 AC 1,544 ms
322,048 KB
testcase_16 AC 1,600 ms
323,840 KB
testcase_17 AC 1,546 ms
323,704 KB
testcase_18 AC 1,569 ms
323,328 KB
testcase_19 AC 1,544 ms
322,560 KB
testcase_20 AC 1,530 ms
318,200 KB
testcase_21 AC 1,563 ms
319,976 KB
権限があれば一括ダウンロードができます

ソースコード

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;

    int encode (int i, int set, bool has, bool less) {
        int res = 0;
        int p = 1;
        res += p * i;
        p *= len + 1;
        res += p * set;
        p *= 1 << 10;
        res += p * has;
        p *= 2;
        res += p * less;
        return res;
    }

    auto memo = new long[]((len + 1) * (1 << 10) * 2 * 2);
    memo[] = -1;
    long dp (int i, int set, bool has, bool less) {
        auto key = encode(i, set, has, less);
        if (memo[key] != -1) 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