ダブリングした移動距離を求める

2の冪回操作した後の位置はダブリングで得られる。そして、2の冪回操作した「移動距離」はダブリングした情報を基に累積和っぽいことをすると得られる。

この移動距離は鳩ノ巣原理など周期性を用いても求められることが多いが、ダブリングに慣れていればこちらの方が脳への負担が少ないと思う。

この移動距離の求め方をまとめる。

前提：累積和とダブリングを理解している。

・作り方

ざっくり言うと、 $2^i$ の移動距離と $2^i$ の移動距離を足して $2^{i+1}$ の移動距離を作る。

式としては以下のようになる。

(位置 j から $2^{i+1}$ 回操作した距離) = (位置 j から $2^i$ 回操作した移動距離) + (「位置 j から $2^i$ 回操作した後の位置」から $2^i$ 回操作した移動距離)

イメージとしては以下のようになる。

まず、位置 j にいる

→ 位置 j から $2^i$ 回操作する（位置 j から $2^i$ 回操作した移動距離を足す... ①)

→ 操作後は、「位置 j から $2^i$ 回操作した後の位置」(以下、位置 k ) にいることになる

→ 位置 k からさらに $2^i$ 回操作する (位置 k から $2^i$ 回操作した移動距離を足す... ②)

→ 結果として、位置 j から $2^i$ 回の操作を2回行った移動距離（ = 位置 j から $2^{i+1}$ 回の操作を行った距離）が求まる。

・問題例：ABC179 E - Sequence Sum

問題
x を m で割った余りを f(x, m) とします。
初期値 $A_1 = X$ および漸化式 $A_{n+1} = f({A_n}^2, X)$ で定まる数列を A とします。 $\sum_{i=1}^N{A_n}$ を求めてください。

制約
・1 ≦ N ≦ $10^{10}$
・1 ≦ X < M ≦ $10^5$
・入力は全て整数

まず、値のダブリングを作る。

・dp[i][j]：j を $2^i$ 回操作した値

次に、ダブリングの累積和を作る

・dp_sum[i][j]：j を $2^i$ 回操作した移動距離

累積の式は前述のイメージにならい、以下のように作る

・dp_sum[i + 1][j] = dp_sum[i][j] (これが前述①) + dp_sum[i][dp[i][j]] (これが前述②)

・C++の実装例

#include <bits/stdc++.h>
using namespace std;

int main() {

    long long N;
    int X, M;
    cin >> N >> X >> M;

    // まず普通のダブリングを行う
    vector<vector<int> > dp(35, vector<int>(M));
    for (int i = 0; i < M; i++) dp[0][i] = 1LL * i * i % M;
    for (int i = 0; i < 34; i++) {
        for (int j = 0; j < M; j++) {
            dp[i + 1][j] = dp[i][dp[i][j]];
        }
    }

    // 次に、ダブリングの累積和を行う
    vector<vector<long long> > dp_sum(35, vector<long long>(M));
    for (int i = 0; i < M; i++) dp_sum[0][i] = i;
    for (int i = 0; i < 34; i++) {
        for (int j = 0; j < M; j++) {
            // dp_sum[i + 1][j] := j　を 2^(i+1)回操作した移動距離
            // dp_sum[i][j] := j　を 2^i回操作した移動距離
            // dp_sum[i][dp[i][j]] := 「j　を 2^i回操作した値」を、2^i回操作した移動距離
            dp_sum[i + 1][j] = dp_sum[i][j] + dp_sum[i][dp[i][j]];
        }
    }

    long long ans = 0;
    for (int i = 0; i < 35; i++) {
        if (N & (1LL << i)) {
            // 現在の値Xを2^i回操作する前に、Xから2^i回操作した距離を先に足す
            ans += dp_sum[i][X];
            X = dp[i][X];
        }
    }
    cout << ans << endl; 
    return (0);
}