結果

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

ソースコード

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