結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー SnowBeenDiding
提出日時 2024-08-30 22:13:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 330 ms / 3,000 ms
コード長 2,908 bytes
コンパイル時間 5,420 ms
コンパイル使用メモリ 314,980 KB
実行使用メモリ 169,412 KB
最終ジャッジ日時 2024-08-30 22:14:42
合計ジャッジ時間 11,779 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;
using mint = modint998244353;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {
    int n = v.size();
    rep(i, 0, n) { os << v[i] << " \n"[i == n - 1]; }
    return os;
}

mint solve(string s) {
    int n = s.size();
    vector z0(n + 1, vector(2, mint(0)));
    vector z1(n + 1, vector(2, mint(0)));
    vector z2(n + 1, vector(2, mint(0)));
    z0[0][0] = 1;
    rep(i, 0, n) {
        { // 0->0
            if (s[i] == '0') {
                z0[i + 1][0] += z0[i][0] + z2[i][0];
                z1[i + 1][0] += 0;
                z2[i + 1][0] += z1[i][0];
            } else if (s[i] == '4') {
                z0[i + 1][0] += 0;
                z1[i + 1][0] += z0[i][0] + z1[i][0];
                z2[i + 1][0] += 0;
            } else {
                z0[i + 1][0] += z0[i][0] + z1[i][0] + z2[i][0];
                z1[i + 1][0] += 0;
                z2[i + 1][0] += 0;
            }
        }
        { // 0->1
            rep(j, 0, s[i] - '0') {
                if (j == 0) {
                    z0[i + 1][1] += z0[i][0] + z2[i][0];
                    z1[i + 1][1] += 0;
                    z2[i + 1][1] += z1[i][0];
                } else if (j == 4) {
                    z0[i + 1][1] += 0;
                    z1[i + 1][1] += z0[i][0] + z1[i][0];
                    z2[i + 1][1] += 0;
                } else {
                    z0[i + 1][1] += z0[i][0] + z1[i][0] + z2[i][0];
                    z1[i + 1][1] += 0;
                    z2[i + 1][1] += 0;
                }
            }
        }
        { // 1->1
            rep(j, 0, 10) {
                if (j == 0) {
                    z0[i + 1][1] += z0[i][1] + z2[i][1];
                    z1[i + 1][1] += 0;
                    z2[i + 1][1] += z1[i][1];
                } else if (j == 4) {
                    z0[i + 1][1] += 0;
                    z1[i + 1][1] += z0[i][1] + z1[i][1];
                    z2[i + 1][1] += 0;
                } else {
                    z0[i + 1][1] += z0[i][1] + z1[i][1] + z2[i][1];
                    z1[i + 1][1] += 0;
                    z2[i + 1][1] += 0;
                }
            }
        }
    }
    auto debug = [&](auto z) {
        rep(i, 0, n + 1) {
            rep(j, 0, 2) cerr << z[i][j].val() << " \n"[j == 1];
        }
    };
    mint ans = 0;
    rep(i, 0, 2) ans += z0[n][i] + z1[n][i] + z2[n][i];
    ans--;
    // cout << ans.val() << endl;
    return ans;
}

mint don(string s) {
    int ret = 0;
    int n = stoll(s);
    rep(i, 1, n + 1) {
        string t = to_string(i);
        if (t.find("404") != string::npos) {
            ret++;
        }
    }
    return (mint)n - ret;
}

int main() {
    string s;
    cin >> s;
    cout << solve(s).val() << endl;
}
0