AtCoderダブリング問題総まとめ（中３女子しらべ）

こんにちわ！中３女子です！！！

ABC367 Eのダブリング問題が解けなかったのが悔しくて過去問を12問解きました☆  
AtCoder上で解けるダブリング問題12問と実装時のポイントやパターンをまとめたのでごさしゅうください！

ダブリング問題が解けるようになると自然と内から自信が満ち溢れてくるはずですし、気になるひとにダブリングの解説をした日にはそれはもういちころのはずです！ダブリングを上手に使えるようになって恋人をゲットです!?（ぐるぐる目）

## 対象読者

緑コーダー周辺のひとにぶっさされです！

## おすすめの精進管理ツール

お兄ちゃんたち、もしかして精進もしてないのに結果がでないとかゆってないよね？？？  
あっとーてき精進でライバルに差をつけるです！

[AtCoder精進チャート](https://a-tilol.github.io/atcoder-shojin-chart-nextjs/)
![shojin-chart2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/260154/f0ecc694-86ea-7e4d-319e-17714f31bc1e.gif)

つくったのでつかって☆

## ダブリング問題一覧

問題を解く方はこちらをどうぞ！  
ダブリング解法で個人的に解きやすかった順（てきとー）です

- [D - Teleporter](https://atcoder.jp/contests/abc167/tasks/abc167_d) Diff 754
  - ダブリングやるです！
- [A57 - Doubling](https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_be)
  - クエリ形式の問題です！
- [D - Gathering Children](https://atcoder.jp/contests/abc136/tasks/abc136_d) Diff 794
- [058 - Original Calculator（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_bf) Diff 1199
- [E - Permute K times](https://atcoder.jp/contests/abc367/tasks/abc367_e) Diff 1370
  - この記事のきっかけとなった問題です。ありがと
- [D - 阿弥陀](https://atcoder.jp/contests/abc013/tasks/abc013_4) Diff 1730
  - あみだくじたのしー！
- [E - Putting Candies](https://atcoder.jp/contests/abc241/tasks/abc241_e) Diff 1248
- [E - Packing Potatoes](https://atcoder.jp/contests/abc258/tasks/abc258_e) Diff 1545
  - 合わせ技です！
- [E - Sequence Sum](https://atcoder.jp/contests/abc179/tasks/abc179_e) Diff 1175
  - 和をとるパターンです！
- [E - Geometric Progression](https://atcoder.jp/contests/abc293/tasks/abc293_e) Diff 1453
  - こうさつー！
- [D - Moving Piece](https://atcoder.jp/contests/abc175/tasks/abc175_d) Diff 1491
  - 解説みてもダブリング解法はちょっとよくわかってない。お兄ちゃん教えて
- [D - へんてこ辞書](https://atcoder.jp/contests/abc030/tasks/abc030_d) Diff 1586
  - （おまけ）問題文は一見ダブリングだけど遷移回数が$10^{100000}$です！

## ダブリング問題の頻出パターン（中３女子しらべ）

パターンを抑えて得点力あっぷです！

- そのままダブリングすればよいパターン
  - やるです！
- 最初の遷移を工夫して解くパターン
  - 問題文をもとに遷移を作るです！
- DPする値を工夫するパターン（和、積など）
  - 遷移のDPと和のDPの２つをつくるなどするです！
- 繰り返し2乗法部分で工夫して解くパターン
  - 考察してつじつまを合わせるです！

周期性を考えた方が簡単な場合はそっちで解くのもありです！

## ダブリングかんたん解説

### 基本的な問題設定

長さ$N$の数列 $A_1~A_2~\dots~A_N$ が与えられる。数列$A$の位置$i$にいるとき、遷移先を位置$A_i$とする。はじめ位置$1$にいるとして、$K$回遷移を繰り返した後の位置を求めよ →[実際の問題例](https://atcoder.jp/contests/abc167/tasks/abc167_d)

多くの場合Kが非常に大きいため($K≦10^{18}$など)、愚直にシミュレーションすると間に合いません。プロセッサさんもっとがんばって！

### ダブリングのアルゴリズム

1. DPにより2の累乗回遷移したときの位置をあらかじめ求めます

   $dp[i][j]$を位置$j$から$2^i$回遷移したときの位置とすると、$2^{i+1}$回遷移したときの位置は以下の漸化式で求められます

    $$dp[i+1][j] = dp[i][dp[i][j]]$$

    上手くいくことの説明  
    $dp[i][j]$が位置$j$から$2^i$回遷移したときの位置であるため、その位置からさらに$2^i$回遷移した位置が $2^i + 2^i$ で $2^{i+1}$回遷移した位置になります

2. 任意の整数$K$は$2$の累乗の和で表せるため、$K$回遷移した後の位置は繰り返し2乗法を用いて求めることができます

求める遷移を$2$の累乗回の場合に絞ることができるため、$K$回の遷移の導出に必要な計算量を $O(NlogK)$ に落とすことができます！すごいね！！

「$2$の累乗回の遷移先が高速で求まる」と、「任意の整数が$2$の累乗の和に高速に分解できる」の2つがかみ合ってて良き！

#### Pythonによる実装例

同じ問題設定の問題 [D - Teleporter](https://atcoder.jp/contests/abc167/tasks/abc167_d)

```python
import math

N, K = list(map(int, input().split()))
M = int(math.log2(K)) + 1
A = list(map(int, input().split()))
A = [e - 1 for e in A]  # 0-indexedにする

# 2^i回目の遷移先をiの小さいほうから求める
dp = [[0] * N for _ in range(M)]
dp[0] = A
for i in range(M - 1):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

# 繰り返し2乗法によりK回目の遷移先を求める
ans = 0  # 初期位置0で初期化
i = 0
while K > 0:
    if K % 2:
        ans = dp[i][ans]
    i += 1
    K >>= 1
print(ans + 1)  # 0-indexedにした場合は忘れずに+1
```

## ひとこと解説 & 実装例

わたしが最初に思いついた解法を紹介しています  
他の解法については公式解説をみて！

### [D - Teleporter](https://atcoder.jp/contests/abc167/tasks/abc167_d) Diff 754

#### [ダブリング解法](https://atcoder.jp/contests/abc167/submissions/56968905)

そのままダブリングすればよいパターンです！

制約がK≦10^18でlog2(K)<60なので2^60までDPで求めればいいですね

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 60
N, K = rints()
A = [e - 1 for e in rints()]

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

ans = 0
p = 0
while K > 0:
    if K & 1:
        ans = dp[p][ans]
    p += 1
    K >>= 1
print(ans + 1)
```

##### 定数倍高速化のポイント

位置jから2^i回遷移したときの位置をdp[i][j]で管理していますが、インデックスを逆にしてdp[j][i]のように管理すると配列アクセスでキャッシュミスが起こりやすくなり遅くなるので気をつけましょう  
問題によってはTLEするかもです

dp[i][j]の場合 **244**ms  
dp[j][i]の場合 **731**ms

この問題では3倍くらい差が出ます

#### [周期性を利用した解法](https://atcoder.jp/contests/abc167/submissions/56970344)

遷移をグラフにすると、各頂点はある1つの頂点への有向辺を持つグラフ（Functional Graph）となります  
Functional Graphは遷移を繰り返すと最終的にサイクルに入るのでその周期性を利用することでも解くことができます  
O(N)で解けるので計算量的にはこちらの方が良いです

ダブリングが上手く書けない場合は周期性で解くのもありです！  
問題や自分との相性で使い分けると良さめです

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

N, K = rints()
A = [e - 1 for e in rints()]

# サイクルの始まりを探索
T = [0]
ind = {0: 0}
cycle_start = -1
for i in range(N):
    nxt = A[T[-1]]
    if nxt in ind:
        cycle_start = ind[nxt]
        break
    T.append(nxt)
    ind[nxt] = i + 1

if len(T) > K:
    # サイクルに入る前に終わる場合
    print(T[K] + 1)
else:
    # サイクルに入る場合
    print(T[cycle_start + (K - cycle_start) % len(T[cycle_start:])] + 1)
```

### [A57 - Doubling](https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_be)

#### [ダブリング解法](https://atcoder.jp/contests/tessoku-book/submissions/56974485)

そのままダブリングすればよいパターンです！  

ダブリングしてクエリに順に答えればOK

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

M = 30
N, Q = rints()
A = rdecints()

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

for _ in range(Q):
    x, y = rints()
    x -= 1
    p = 0
    while y > 0:
        if y & 1:
            x = dp[p][x]
        p += 1
        y >>= 1
    print(x + 1)
```

### [D - Gathering Children](https://atcoder.jp/contests/abc136/tasks/abc136_d) Diff 794

#### [ダブリング解法](https://atcoder.jp/contests/abc136/submissions/56887533)

最初の遷移を工夫して解くパターンです！

LRで場合分けして最初の遷移を求めてダブリングです

```python
import sys

M = 17
s = input()
N = len(s)

A = [0] * N
for i in range(N):
    if s[i] == "R":
        A[i] = i + 1
    else:
        A[i] = i - 1

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

ans = [0] * N
for i in range(N):
    ans[dp[M][i]] += 1
print(*ans)
```

### [058 - Original Calculator（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_bf) Diff 1199

#### [ダブリング解法](https://atcoder.jp/contests/typical90/submissions/56989855)

最初の遷移を工夫して解くパターンです！

MOD10^5より遷移先の値は0～10^5-1なので、問題文中の１～３の処理を0～10^5-1に対して行い1回目の遷移行列を求めます  
あとはダブリングして終わりです！

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 60
L = int(1e5)
N, K = rints()

A = list(range(L))  # 最初の遷移を入れる配列
for i in range(L):
    j = i
    y = 0
    while j > 0:
        y += j % 10
        j //= 10
    A[i] = (i + y) % L

dp = [[0] * L for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(L):
        dp[i + 1][j] = dp[i][dp[i][j]]

ans = N
p = 0
while K > 0:
    if K & 1:
        ans = dp[p][ans]
    p += 1
    K >>= 1
print(ans)
```

### [E - Permute K times](https://atcoder.jp/contests/abc367/tasks/abc367_e) Diff 1370

#### [ダブリング解法](https://atcoder.jp/contests/abc367/submissions/56974345)

そのままダブリングすればよいパターン＋微考察です！

問題文の通りAへの操作を考えるとむずかしいですが、Xの遷移を考えればよいことに気づけばダブリングして終わりです

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

M = 60
N, K = rints()
X = rdecints()
A = rints()

dp = [[0] * N for _ in range(M)]
dp[0] = X
for i in range(M - 1):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

ind = list(range(N))
p = 0
while K > 0:
    if K & 1:
        for i in range(N):
            ind[i] = dp[p][ind[i]]
    p += 1
    K >>= 1

print(*[A[i] for i in ind])
```

### [D - 阿弥陀](https://atcoder.jp/contests/abc013/tasks/abc013_4) Diff 1730

#### [ダブリング解法](https://atcoder.jp/contests/abc013/submissions/56990629)

最初の遷移を工夫して解くパターンです！

問題が長いですが要は1つのあみだくじが1つの遷移を表すので、１つのあみだくじから最初の遷移を作成してダブリングです！

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

P = 30
N, M, D = rints()
A = rdecints()

X = list(range(N))
for a in reversed(A):
    X[a], X[a + 1] = X[a + 1], X[a]

dp = [[0] * N for _ in range(P + 1)]
dp[0] = X
for i in range(P):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

p = 0
ans = list(range(N))
while D > 0:
    if D & 1:
        for i in range(N):
            ans[i] = dp[p][ans[i]]
    p += 1
    D >>= 1

for e in ans:
    print(e + 1)
```

### [E - Putting Candies](https://atcoder.jp/contests/abc241/tasks/abc241_e) Diff 1248

#### [ダブリング解法](https://atcoder.jp/contests/abc241/submissions/56989773)

DPする値を工夫するパターンです！

遷移先はX%Nなので、dp[i][j]=アメj個所持時に2^i回遷移したときに得られるアメの個数とすれば  
dp[i + 1][j] = dp[i][j] + dp[i][(j + dp[i][j]) % N] とできます！

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 40
N, K = rints()
A = rints()

dp = [[0] * N for i in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][j] + dp[i][(j + dp[i][j]) % N]

ans = 0
i = 0
while K > 0:
    if K & 1:
        ans += dp[i][ans % N]
    i += 1
    K >>= 1
print(ans)
```

### [E - Packing Potatoes](https://atcoder.jp/contests/abc258/tasks/abc258_e) Diff 1545

#### [ダブリング解法](https://atcoder.jp/contests/abc258/submissions/56991269)

最初の遷移を工夫して解くパターンです！

重さWiのi番目のじゃがいもから箱に詰め始めたとき、次の箱に入れる最初のじゃがいもが何番目になるかの遷移を考えればよいです。
その際にi番目からはじめたときに箱に入るじゃがいもの個数も同時に数えておきます。以下の実装では累積和＋にぶたんで求めています

```python
import sys
rint = lambda: int(sys.stdin.readline())
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 40
N, Q, X = rints()
W = rints()

cumW = [0] * (N + 1)    # ジャガイモの重さの累積和
for i in range(N):
    cumW[i + 1] += cumW[i] + W[i]

cnt = [0] * N   # i番目から始めたときに箱に入るじゃがいもの数
A = [0] * N     # i番目から始めたときに次の箱に最初に入るじゃがいもの番号
for i in range(N):
    L, r = 1, int(2e9) + 1
    while L < r:
        m = (L + r) // 2
        s = (i + m) // N * cumW[-1] - cumW[i] + cumW[(i + m) % N]
        if s >= X:
            r = m
        else:
            L = m + 1
    A[i] = (i + L) % N
    cnt[i] = L

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

for _ in range(Q):
    K = rint() - 1
    j = 0
    i = 0
    while K > 0:
        if K & 1:
            j = dp[i][j]
        i += 1
        K >>= 1
    print(cnt[j])
```

### [E - Sequence Sum](https://atcoder.jp/contests/abc179/tasks/abc179_e) Diff 1175

#### [ダブリング解法](https://atcoder.jp/contests/abc179/submissions/56991577)

最初の遷移を工夫して解くパターン + DPする値を工夫するパターンです！

mod MなのでM未満の整数aに対してf(a^2, M)を計算し最初の遷移を求めます  
あとはダブリング、と言いたいところですが答えが和なので工夫が必要です  
遷移先のDPに加え、dp_sum[i][j] = jから2^i回遷移したときの和、として管理することで解くことができます

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

P = 34
N, X, M = rints()

dp_a = [[0] * M for _ in range(P + 1)]
dp_sum = [[0] * M for _ in range(P + 1)]
for i in range(M):
    dp_a[0][i] = i * i % M
    dp_sum[0][i] = i

for i in range(P):
    for j in range(M):
        dp_a[i + 1][j] = dp_a[i][dp_a[i][j]]
        dp_sum[i + 1][j] = dp_sum[i][j] + dp_sum[i][dp_a[i][j]]

ans = 0
p = 0
while N > 0:
    if N & 1:
        ans += dp_sum[p][X]
        X = dp_a[p][X]
    p += 1
    N >>= 1
print(ans)
```

#### [周期性を利用した解法](https://atcoder.jp/contests/abc179/submissions/56991713)

ダブリング解法の和のDPが思いつかない場合（わたしのこと）は周期性を利用して解くことができます

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

N, X, M = rints()
A = [X]
d = {X: 0}
cycle_start = -1
for i in range(1, N):
    X = X * X % M
    if X in d:
        cycle_start = d[X]
        break
    A.append(X)
    d[X] = i

ans = 0
if cycle_start == -1:
    ans = sum(A)
else:
    cycle_sum = sum(A[cycle_start:])
    cycle_len = len(A[cycle_start:])
    ans = sum(A[:cycle_start])
    N -= cycle_start
    A = A[cycle_start:]
    ans += N // cycle_len * cycle_sum + sum(A[: N % cycle_len])
print(ans)
```

### [E - Geometric Progression](https://atcoder.jp/contests/abc293/tasks/abc293_e) Diff 1453

#### [ダブリング解法](https://atcoder.jp/contests/abc293/submissions/56992624)

DPする値を工夫するパターン ＋ 繰り返し2乗法部分で工夫して解くパターンです！

dp[i] = A^(2^i)までの和とすると、Kが2の累乗の場合について解けます  
Kが2の累乗以外の場合は困りますが、繰り返し2乗法部分を工夫することで解けます

例えばK=6のとき、6 = 2^1 + 2^2です。素直にdp[1] + dp[2]を考えると、  
dp[1] + dp[2] = (A^0 + A^1) + (A^0 + A^1 + A^2 + A^3) となり答えが合いません

これを見ると、A^2 * dp[2]とすると以下のようになり答えが合いそうです  
dp[1] + A^2 * dp[2] = (A^0 + A^1) + A^2 * (A^0 + A^1 + A^2 + A^3)

あとは実装あるのみです！

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

P = 40
A, X, M = rints()

dp = [0] * (P + 1)
dp[0] = 1
An = A
for i in range(P):
    dp[i + 1] = (dp[i] + An * dp[i]) % M
    An = An * An % M

ans = 0
pad = 0
p = 0
while X > 0:
    if X & 1:
        ans += pow(A, pad, M) * dp[p]
        ans %= M
        pad += 1 << p
    p += 1
    X >>= 1
print(ans)
```

#### [等比級数の和を計算する解法](https://atcoder.jp/contests/abc293/submissions/56992827)

個人的には[kyopro_friendsさんの解法](https://atcoder.jp/contests/abc293/editorial/5966)がシンプルで好きでした

mod Mにおいてaの逆元が存在しない場合はmod M*aで計算しておいてaで割る、は覚えておきたいテクニックでした

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

A, X, M = rints()
if A == 1:
    print(X % M)
    exit()

K = M * (A - 1)
a = A
Ax = 1
while X > 0:
    if X & 1:
        Ax = Ax * a % K
    a = a * a % K
    X >>= 1
print((Ax - 1) // (A - 1) % M)
```

### [D - Moving Piece](https://atcoder.jp/contests/abc175/tasks/abc175_d) Diff 1491

#### ダブリング解法

ごめんにゃさい。。解説をみてもよく分かりませんでした。

賢明なみなさんは分かると思うので[けんちょんさんの解説](https://drken1215.hatenablog.com/entry/2020/08/17/182700)の解法(2)をご覧ください

#### [周期性を用いた解法](https://atcoder.jp/contests/abc175/submissions/56919462)

全ての開始位置を試して最大値を出力します  
Pが順列という制約を読み飛ばしてしまったのでごちゃごちゃなコードになっていますが一応ACです（ひどい）  

Pが順列だとどこから始めてもしっぽの無いサイクルになるのでもう少し楽に解けます

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

INF = int(1e18 + 1)
N, K = rints()
P = rdecints()
C = rints()

ans = -INF
for x in range(N):
    A = [P[x]]
    d = {P[x]: 0}
    cycle_start = -1
    for i in range(K - 1):
        na = P[A[i]]
        if na in d:
            cycle_start = d[na]
            break
        A.append(na)
        d[na] = i + 1

    t = 0
    for a in A:
        t += C[a]
        ans = max(ans, t)

    if cycle_start == -1:
        continue

    cycle_sum = sum(C[e] for e in A[cycle_start:])
    if cycle_sum <= 0:
        continue

    t = sum(C[e] for e in A[:cycle_start])
    A = A[cycle_start:]
    k = K - cycle_start
    cycle_len = len(A)
    t += k // cycle_len * cycle_sum
    ans = max(ans, t)

    tt = t
    for i in range(k % cycle_len):
        tt += C[A[i]]
        ans = max(ans, tt)

    if k // cycle_len == 0:
        continue

    for i in range(cycle_len):
        t -= C[A[-i]]
        ans = max(ans, t)

print(ans)
```

### [D - へんてこ辞書](https://atcoder.jp/contests/abc030/tasks/abc030_d) Diff 1586

遷移回数が10^100000なのでさすがのダブリングさんでもTLEですね。log2(10^100000)を計算する気にもなりません。調べた結果332192くらいでした。O(Nlogk)なのでやっぱり無理ですね

#### [周期性を利用した解法](https://atcoder.jp/contests/abc030/submissions/56993609)

サイクルの周期Tが求まればk%Tなどして解けそうです  
ただし、kが大きくて数値として扱えないので一桁ずつ処理する工夫が必要です

```python
import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

N, a = rints()
k = input()
b = rdecints()
a -= 1

mem = [a]
d = {a: 0}
cycle_start = -1
for i in range(1, N + 1):
    nx = b[mem[-1]]
    if nx in d:
        cycle_start = d[nx]
        break
    mem.append(nx)
    d[nx] = i

# サイクルに入る前にk回になる場合
if len(str(cycle_start)) > len(k) or (
    len(str(cycle_start)) == len(k) and cycle_start >= int(k)
):
    print(mem[int(k)] + 1)
    exit()

# kを一桁ずつ処理して(k-cycle_start)%cycle_lenを求める
cycle_len = len(mem[cycle_start:])
L = 0
for ki in k:
    L = (L * 10 + int(ki)) % cycle_len
L = (L - cycle_start) % cycle_len
print(mem[cycle_start + L] + 1)
```

## おわりに

中３女子に不慣れなので語尾が安定しにゃい