結果

問題 No.2772 Appearing Even Times
コンテスト
ユーザー InTheBloom
提出日時 2026-04-10 14:51:31
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
TLE  
実行時間 -
コード長 1,714 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 666 ms
コンパイル使用メモリ 172,440 KB
実行使用メモリ 309,788 KB
最終ジャッジ日時 2026-04-10 14:51:56
合計ジャッジ時間 6,566 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/internal/hash.d(298): Warning: cannot inline function `core.internal.hash.hashOf!(const(void)*).hashOf`
size_t hashOf(T)(scope const T val, size_t seed) if (__traits(isScalar, T) && !is(T == __vector))
       ^
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/internal/newaa.d(114): Warning: cannot inline function `core.internal.newaa.compat_key!(State, State).compat_key`
private ref compat_key(K, K2)(ref K2 key)
            ^
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/internal/newaa.d(187): Warning: cannot inline function `core.internal.newaa.pure_hashOf!(State).pure_hashOf`
        hash_t pure_hashOf(scope const ref K key) @trusted { return hashOf(cast()key); }
               ^
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/internal/hash.d(298): Warning: cannot inline function `core.internal.hash.hashOf!(void*).hashOf`
size_t hashOf(T)(scope const T val, size_t seed) if (__traits(isScalar, T) && !is(T == __vector))
       ^
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/internal/newaa.d(205): Warning: cannot inline function `core.internal.newaa.pure_keyEqual!(State, State).pure_keyEqual`
        bool pure_keyEqual(ref const K1 k1, ref const K2 k2) @trusted { return cast()k1 == cast()k2; }
             ^

ソースコード

diff #
raw source code 

import std;

void main () {
    const long MOD = 998244353;
    auto N = readln.chomp.map!(a => a - '0').array;

    struct DPVal {
        long val;
    }
    struct State {
        int cur;
        bool less;
        int mp;

        Tuple!(bool, State) update (int next) {
            State nstate;
            if (!less && N[cur] < next) {
                return tuple(false, nstate);
            }
            nstate.cur = cur + 1;
            nstate.less = less || next < N[cur];
            nstate.mp = mp ^ (1 << next);

            return tuple(true, nstate);
        }
        bool isEnd () {
            return cur == N.length;
        }
        DPVal endValue () {
            if (mp == 0) {
                return DPVal(1L);
            }
            return DPVal(0L);
        }
    }

    DPVal[State] memo;
    DPVal f (State state) {
        if (state in memo) {
            return memo[state];
        }
        if (state.isEnd()) {
            return memo[state] = state.endValue();
        }

        DPVal ret;
        foreach (next; 0 .. 10) {
            auto nstate = state.update(next);
            if (!nstate[0]) {
                continue;
            }

            auto nval = f(nstate[1]);
            ret.val += nval.val;
        }
        ret.val %= MOD;

        return memo[state] = ret;
    }

    // i文字目からスタート
    long ans = 0;
    foreach (i; 0 .. N.length.to!int) {
        int up = N[i];
        if (0 < i) {
            up = 9;
        }

        foreach (n; 1 .. up + 1) {
            bool less = (0 < i) || n < up;
            auto st = State(i + 1, less, 1 << n);
            ans += f(st).val;
        }
        ans %= MOD;
    }

    writeln(ans);
}
0