結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー norioc
提出日時 2026-01-06 00:20:13
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,526 ms / 3,000 ms
コード長 2,409 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,989 ms
コンパイル使用メモリ 354,336 KB
実行使用メモリ 13,104 KB
最終ジャッジ日時 2026-01-06 00:20:40
合計ジャッジ時間 27,209 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 998244353;

// 状態キー
// (leading zero, 状態, 未満フラグ)
struct State {
    bool lz;
    int st;
    bool lt;

    bool operator<(const State& other) const {
        if (lz != other.lz) return lz < other.lz;
        if (st != other.st) return st < other.st;
        return lt < other.lt;
    }
};

vector<pair<State, long long>> transition(const State& k, long long v, int x) {
    vector<pair<State, long long>> res;
    bool lz = k.lz;
    int st = k.st;
    bool lt = k.lt;

    if (lz) {
        for (int d = 1; d <= 9; d++) {
            int nst = (d == 4 ? 1 : 0);
            res.push_back({{false, nst, true}, 1});
        }
        // leading zero 維持
        res.push_back({{true, 0, true}, 1});
    } else {
        for (int d = 0; d <= 9; d++) {
            if (!lt && d > x) break;
            if (st == 2 && d == 4) continue; // 404 を禁止

            int nst = 0;
            if (st == 0 && d == 4) nst = 1;
            else if (st != 0 && d == 4) nst = 1;
            else if (st == 1 && d == 0) nst = 2;

            bool nlt = lt || (d < x);
            res.push_back({{false, nst, nlt}, v});
        }
    }
    return res;
}

map<State, long long> accum_dp(
    const vector<int>& xs,
    map<State, long long> init,
    bool is_reset = true
) {
    map<State, long long> dp = init;

    for (int x : xs) {
        map<State, long long> pp;
        if (!is_reset) pp = dp;

        swap(dp, pp);

        for (auto& [fm_key, fm_val] : pp) {
            auto nexts = transition(fm_key, fm_val, x);
            for (auto& [to_key, to_val] : nexts) {
                long long& ref = dp[to_key];
                ref = (ref + to_val) % MOD;
            }
        }
    }
    return dp;
}

int main() {
    string N;
    cin >> N;

    vector<int> digits;
    for (char c : N) digits.push_back(c - '0');

    map<State, long long> init;
    init[{true, 0, true}] = 1;

    for (int d = 1; d <= digits[0]; d++) {
        bool lz = false;
        int st = (d == 4 ? 1 : 0);
        bool lt = (d < digits[0]);
        init[{lz, st, lt}]++;
    }

    vector<int> rest(digits.begin() + 1, digits.end());
    auto dp = accum_dp(rest, init);

    long long res = 0;
    for (auto& [k, v] : dp) {
        if (k.lz) continue;
        res = (res + v) % MOD;
    }

    cout << res << '\n';
    return 0;
}
0