結果

問題 No.3242 Count 8 Included Numbers (Hard)
コンテスト
ユーザー norioc
提出日時 2026-01-05 00:19:41
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 785 ms / 2,000 ms
コード長 2,022 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,771 ms
コンパイル使用メモリ 354,592 KB
実行使用メモリ 18,216 KB
最終ジャッジ日時 2026-01-05 00:19:58
合計ジャッジ時間 15,682 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

static const long long MOD = 998244353;

// 状態遷移関数
// k = (8が含まれるか, 未満か)
// v = 現在の個数
// ix = (桁index, 上限digit)
vector<pair<pair<bool, bool>, long long>>
f(pair<bool, bool> k, long long v, pair<int, int> ix) {
    bool b = k.first;
    bool lt = k.second;
    int digit = ix.second;

    vector<pair<pair<bool, bool>, long long>> res;
    for (int d = 0; d <= 9; ++d) {
        bool nb = b || (d == 8);
        if (lt) {
            res.push_back({{nb, lt}, v});
        } else if (d <= digit) {
            bool nlt = d < digit;
            res.push_back({{nb, nlt}, v});
        }
    }
    return res;
}

// 加算用 op
long long op(long long a, long long b) {
    return (a + b) % MOD;
}

// accum_dp 相当
map<pair<bool, bool>, long long>
accum_dp(
    const vector<pair<int, int>>& xs,
    map<pair<bool, bool>, long long> init
) {
    map<pair<bool, bool>, long long> dp = init;

    for (auto ix : xs) {
        map<pair<bool, bool>, long long> next_dp;
        for (auto& [key, val] : dp) {
            for (auto& [to_key, to_val] : f(key, val, ix)) {
                next_dp[to_key] = op(next_dp[to_key], to_val);
            }
        }
        dp.swap(next_dp);
    }
    return dp;
}

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

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

    // 初期化（先頭桁）
    map<pair<bool, bool>, long long> init;
    for (int d = 0; d <= 9; ++d) {
        if (d <= digits[0]) {
            bool b = (d == 8);
            bool lt = d < digits[0];
            init[{b, lt}]++;
        }
    }

    // 残りの桁
    vector<pair<int, int>> xs;
    for (int i = 1; i < (int)digits.size(); ++i) {
        xs.emplace_back(i, digits[i]);
    }

    auto dp = accum_dp(xs, init);

    long long res = 0;
    for (auto& [key, val] : dp) {
        if (key.first) {
            res = (res + val) % MOD;
        }
    }

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