abc129 F - Takahashi's Basics in Education and Learning

#数式変形 #二分累乗法

youtube editorial の解読

数列の, k 桁の数の数列を考える
A, A + B, A + 2B
A は入力の A とは別で, k 桁の数列の初項

3 項だけだとすると
A + 2B はそのまま足され, A + B は 10^k されて足され,
A は $10^{2k}$ されて足される
(実際は, k + 1 桁以降の分も 10 倍されて足される)

$\sum_{i = 0}^{l - 1} (A + B i) 10^{k^{l - i - 1}}$
l - i - 1 は i と変えても同じ
$\sum_{i = 0}^{l - 1} (A + B i) 10^{k^{i}}$

分解
$\sum_{i = 0}^{l - 1} A 10^{k^{i}}$
$\sum_{i = 0}^{l - 1} B i 10^{k^{i}}$

上から考える
A は外に出して,
$f(l) = \sum_{i = 0}^{l - 1} 10^{k^{i}}$
を考える
f(l) を計算量 log l で求めるには
f(l + 1), f(2 * l) と f(l) の関係が求められたらいい

$f(l + 1) = f(l) * 10^k + 1$
k = 2 とすると,
f(2) = 1 + 100
f(3) = 1 + 100 + 10000 = 1 + (1 + 100) 100

f(6) = 1 + 10^2 + 10^4 + 10^6 + 10^8 + 10^{10}
f(2) から 2l - l = l 項増えてる
$f(2l) = f(l) * 10^{k^{l}} + f(l)$

次に,
$g(l) = \sum_{i = 0}^{l - 1} B i 10^{k^{l - i - 1}}$
を考える

B = 4, k = 2 とする
g(2) = 00 04
g(3) = 00 04 08
$g(l + 1) = g(l) * 10^k + B l$

g(6) = 00 04 08 12 16 20
g(3) = 00 04 08 からどう作るか
2l - l = 3 項分 g(3) が 10^2 倍される
g(3) * 10^6 + g(3) = 00 04 08 00 04 08

これで g(6) との差は 12 12 12
$g(2l) = g(l) * 10^{k^l} + g(l) + B l f(l)$

あとは, 桁ごとに独立して解いたのをつなげる

youtube editorial
https://www.youtube.com/watch?v=L8grWxBlIZ4

code reading

コード
Submission #5861224 - AtCoder Beginner Contest 129

ans の計算の流れ
sample1
3, 7, 11, 15, 19
37 (1 桁)
37111519 (2 桁)
となる
37 の次, 37 を111519 の分 10 倍して 111519 を足す

ll b, ten;
 
// x^t
mint pow_(mint x, ll t) { 
  if (t == 0) return 1;
  if (t%2 == 1) {
    return pow_(x, t - 1) * x;
  } else {
    mint y = pow_(x, t / 2);
    return y * y;
  }
}
 
mint f(ll l) {
  if (l == 0) return 0;
  if (l % 2 == 1) {
    ll pl = l - 1;
    return f(pl) * ten + 1;
  } else {
    ll pl = l / 2;
    mint x = f(pl);
    return x * pow_(ten, pl) + x;
  }
}

mint g(ll l) {
  if (l == 0) return 0;
  if (l%2 == 1) {
    ll pl = l-1;
    mint x = g(pl);
    return x*ten + mint(b) * pl;
  } else {
    ll pl = l / 2;
    mint x = g(pl);
    return x * pow_(ten, pl) + x + mint(b) * pl * f(pl);
  }
}
 
int main() {
  ll L, a;
  cin >> L >> a >> b >> mod;
  ll last = a + b * (L - 1); // 数列の末項
  mint ans = 0;
  ten = 10;
  /* 数列における, 各桁の数の初項と末項を求める
  その桁の数列の数の個数も自動的に求まる */
  for (int i = 1; i <= 18; ++i, ten *= 10) {
    ll l = ten / 10, r = ten - 1;
    if (last < l) continue; // 数列自体の末項が左端より小さい
    if (a > r) continue;
    ll na = 0; // [l, r] における初項
    ll nl = 0; // [l, r] における数列の数の個数
    {
      if (a >= l) na = a;
      /* continue されてない中で数列自体の初項が左端以上なら, 
          [l, r] における数列の初項は数列自体の初項 */
      else {
      /* 数列の項だから a + b * i の形でかける
          前提として, a < l (else より) */
      /* l 以降の最初の要素
          l = a + b * i から i を求め, 切り上げ */
      na = (l - a + (b - 1)) / b * b + a; 
    }
    {
      ll nlast = 0;
      /* 数列自体の末項が右端以下なら, 
          [l, r] における末項は数列自体の末項 */
      if (last <= r) nlast = last;
      else {
      /* 前提として r < last
          ([l, r] の末項は数列自体の末項より小さい) */
        nlast = (r - a) / b * b + a;
      }
      nl = (nlast - na) / b + 1; // [l, r] の数列の項数
    }
    ans *= pow_(ten, nl); // 最初 0 にかけても 0
    ans += f(nl) * na;
    ans += g(nl);
  }
  cout << ans.x << endl;
  return 0;
}