結果
問題 | No.2867 NOT FOUND 404 Again |
ユーザー |
![]() |
提出日時 | 2024-08-30 22:00:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 395 ms / 3,000 ms |
コード長 | 1,360 bytes |
コンパイル時間 | 3,703 ms |
コンパイル使用メモリ | 281,744 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-30 22:00:52 |
合計ジャッジ時間 | 10,983 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using namespace atcoder;using ll = long long;using P = pair<ll,ll>;#define fix(x) fixed << setprecision(x)#define asc(x) x, vector<x>, greater<x>#define rep(i, n) for(ll i = 0; i < n; ++i)#define all(x) (x).begin(),(x).end()template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}constexpr ll INFLL = (1LL << 62), MOD = 998244353;constexpr int INF = (1 << 30);using mint = modint998244353;int main(){cin.tie(nullptr);ios::sync_with_stdio(false);string x;cin >> x;vector<mint> dp(100,0);bool ok = true;int n = x.size(), state = 0;rep(i,n){vector<mint> upd(100,0), tot(10,0);rep(j,100) tot[j%10] += dp[j];rep(j,10){rep(k,10){upd[j*10+k] += tot[j];}}upd[4] -= dp[40];if(ok){rep(j,(int)(x[i]-'0')){if(state==40 && j==4) continue;upd[(state*10+j)%100] += 1;}}state = state * 10 + x[i] - '0';if(state==404) ok = false;state %= 100;dp = upd;}mint tot = ok-1;rep(i,100) tot += dp[i];cout << tot.val() << '\n';return 0;}