結果
問題 |
No.3242 Count 8 Included Numbers (Hard)
|
ユーザー |
|
提出日時 | 2025-08-23 02:55:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 946 bytes |
コンパイル時間 | 877 ms |
コンパイル使用メモリ | 98,536 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-23 02:55:29 |
合計ジャッジ時間 | 2,570 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 20 |
ソースコード
#include <iostream> #include <utility> #include <algorithm> #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { std::string N; std::cin >> N; // dp[0] = number of occurrences without 8 // dp[1] = number of occurrences with 8 std::pair<mint, mint> dp; bool seen_eight = false; for (int i = 0; i < N.size(); i++) { std::pair<mint, mint> ndp{dp.first * 9, dp.first + dp.second * 10}; mint num_wo = 0, num_with = 0; if (N[i] == '9') { num_wo = 8; num_with = 1; } else { num_wo = N[i] - '0'; } if (seen_eight) { ndp.second += num_wo + num_with; } else { ndp.first += num_wo; ndp.second += num_with; } seen_eight |= N[i] == '8'; dp = std::move(ndp); } if (seen_eight) dp.second++; std::cout << dp.second.val() << std::endl; }