結果
問題 |
No.2905 Nabeatsu Integration
|
ユーザー |
![]() |
提出日時 | 2024-09-13 19:53:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,610 bytes |
コンパイル時間 | 4,033 ms |
コンパイル使用メモリ | 193,448 KB |
実行使用メモリ | 89,048 KB |
最終ジャッジ日時 | 2024-09-13 19:57:33 |
合計ジャッジ時間 | 41,989 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 TLE * 11 -- * 13 |
ソースコード
#include<iostream> #include<vector> #include<string> #include<unordered_map> using namespace std; using ll = long long; #include <atcoder/all> using namespace atcoder; using mint = modint998244353; int main() { string s; cin >> s; ll n = s.size(); // 各文字列目の時にどの数字を与えるとどのインデックスに移動するか vector q(n + 1, vector<int>(10)); // 正解遷移 for (int i = 0; i < n; i++) q[i][s[i] - '0'] = i + 1; // 不正解の復帰遷移をz-algorithmで調査 auto z = z_algorithm(s); vector<int> revq = { -1,0 }; for (int i = 1; i < n; i++) { ll to = i + z[i]; if (q[to][s[z[i]] - '0'] == 0 && z[i] + 1 < n) { q[to][s[z[i]] - '0'] = z[i] + 1; revq.push_back(z[i] + 1); } } sort(revq.begin(), revq.end()); revq.erase(unique(revq.begin(), revq.end()), revq.end()); unordered_map<int, int> mrev; for (int i = 0; i < revq.size(); i++) mrev[revq[i]] = i; vector<mint> dp(revq.size()); mint r10 = mint(10).inv(); for (int i = n - 1; i >= 0; i--) { vector<mint> ndp(dp.size()); ndp[0] = 1; for (int v = 0; v < 10; v++) { if (q[i][v] == i + 1) { for (int di = 0; di < dp.size(); di++) { ndp[di] += dp[di] * r10; } } else { ndp[mrev[q[i][v]]] += r10; } } if (mrev.find(i) != mrev.end() && mrev[i]) { mint div = (-ndp.back() + 1).inv(); for (int i = 0; i < ndp.size() - 1; i++) { ndp[i] *= div; } ndp.pop_back(); } dp = ndp; } dp[0] -= n - 1; cout << dp[0].val(); return 0; }