結果

問題 No.2772 Appearing Even Times
コンテスト
ユーザー InTheBloom
提出日時 2024-07-18 16:18:31
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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