結果

問題 No.2995 The Ruler Sequence Concatenation
コンテスト
ユーザー Kude
提出日時 2024-12-20 17:34:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,915 bytes
コンパイル時間 3,836 ms
コンパイル使用メモリ 280,072 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-20 17:34:48
合計ジャッジ時間 4,415 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;


// returns (len_of_cycle, first_in-cycle_index)
template<class S, class F>
std::pair<int, int> detect_cycle(F f, S x) {
    S p = x, q = x;
    int l = 0;
    int ub = 1;
    do {
        if (l == ub) {
            ub <<= 1;
            l = 0;
            p = q;
        }
        q = f(q);
        l++;
    } while(p != q);
    p = q = x;
    for(int it = l; it > 0; it--) q = f(q);
    int m = 0;
    while(p != q) p = f(p), q = f(q), m++;
    return {l, m};
}


auto solve(ll n) {
  using mint1 = modint998244353;
  using mint2 = static_modint<998244352>;
  ll p10[19];
  p10[0] = 1;
  rep(i, 18) p10[i+1] = 10 * p10[i];
  n++;
  mint1 ans;
  mint2 len;
  for (int k = 1; p10[k-1] < n; k++) {
    ll l = p10[k - 1], r = min(p10[k], n);
    auto f = [&](mint2 x) { return 2 * x + k; };
    auto g = [&](mint1 v, mint2 len) {
      mint1 c1 = mint1(10).pow(len.val());
      mint1 c0 = c1 * mint1(10).pow(k) + 1;
      return pair(v * c0 + l * c1, f(len));
    };
    auto [period, idx] = detect_cycle(f, len);
    rep(_, idx) {
      if (l == r) break;
      tie(ans, len) = g(ans, len);
      l++;
    }
    if (l == r) continue;
    ll rest = r - l;
    ll q = rest / period, rem = rest % period;
    if (q) {
      vector<mint1> c0s(period);
      {
        mint2 t = len;
        rep(i, period) {
          c0s[i] = mint1(10).pow(t.val() + k) + 1;
          t = f(t);
        }
        assert(t == len);
      }
      mint1 r = 1;
      rep(i, period) r *= c0s[i];
      ans *= r.pow(q - 1);
      vector<mint1> c1s(period);
      {
        mint2 t = len;
        rep(i, period) {
          mint1 c1 = mint1(10).pow(t.val());
          // l+i, l+i+p, ..., l+i+(q-1)p
          // r^(q-1),r^(q-2), ..., 1
          assert(r == 1);
          ll s = l + i;
          c1s[i] = mint1(2 * (l + i) + (q - 1) * period) * q / 2;
          c1s[i] *= c1;
          t = f(t);
        }
      }
      rep(i, period) {
        ans *= c0s[i];
        ans += c1s[i];
      }
      l += q * period;
    }
    rep(_, rem) tie(ans, len) = g(ans, len), l++;
  }
  return ans;
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  cout << solve(n).val() << '\n';
}
0