結果
問題 | No.2995 The Ruler Sequence Concatenation |
ユーザー |
![]() |
提出日時 | 2024-12-18 23:36:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,498 bytes |
コンパイル時間 | 822 ms |
コンパイル使用メモリ | 72,452 KB |
最終ジャッジ日時 | 2025-02-26 15:33:22 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 |
ソースコード
#include <array> #include <cassert> #include <iostream> #include <atcoder/modint> using ll = long long; using mint = atcoder::modint998244353; using mat = std::array<std::array<mint, 3>, 3>; mat mul(mat a, mat b) { mat c; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { c[i][k] += a[i][j] * b[j][k]; } } } return c; } mat id() { mat a; for (int i = 0; i < 3; i++) a[i][i] = 1; return a; } mat pow(mat a, ll e) { mat r = id(); while (e) { if (e & 1) r = mul(r, a); a = mul(a, a); e >>= 1; } return r; } ll pow10(int e) { ll ret = 1; while (e--) ret *= 10; return ret; } int main() { const int tail = 23; const int period = 24; ll n; std::cin >> n; mint ans = 0; mint b = 1; for (int d = 1; pow10(d - 1) <= n; d++) { const mint m = mint(10).pow(d); const ll st = pow10(d - 1); const ll en = std::min(pow10(d), n + 1); ll i = st; while (i < en && (i - st < tail || (en - i) % period != 0)) { ans = (ans * m + i) * b + ans; b *= m * b; i++; } if (i == en) continue; const mint c = b; mat a = id(); for (int k = 0; k < period; k++) { a = mul({{{m * b + 1, b, 0}, {0, 1, 1}, {0, 0, 1}}}, a); b *= m * b; } assert(b == c); const mat res = pow(a, (en - i) / period); ans = res[0][0] * ans + res[0][1] * i + res[0][2]; } std::cout << ans.val() << "\n"; return 0; }