ダブリング - ferinの競プロ帳

この間のABCで話題になってたのでダブリングについてちょっと考えたことのメモ
コードは適当なので雰囲気です

$x:=f(x,y)$ を繰り返す

関数 $f: T \times T \to T$ が存在
$x,y \in T$ について $x := f(x,y)$ を $K$ 回実行
これは $O((f$ の計算量 $) \times \log K)$ で計算可能

繰り返し二乗法などが具体例としてあげられる

template<class T, class F>  
T binpow(T y, ll k, F f, T x) {  
    T ret = x, p = y;  
    while(k > 0) {  
        if(k%2 == 0) {p = f(p, p); k /= 2;}  
        else {ret = f(ret, p); k--;}  
    }  
    return ret;  
};  
  
int main() {  
    // 10^100 mod 1e9+7  
    binpow(10, 100, [](ll a, ll b){ return a*b%1000000007; }, 1);  
}

行列累乗や置換の積を繰り返すような処理も f, x を変更することで対応可能

int main() {  
    // 行列累乗  
    {  
        const ll n = 3; // 行列の次数  
        using mind = modint<1000000007>;  // modintの実装は省略します  
        auto mul = [&](vector<vector<mint>> a, vector<vector<mint>> b) {  
            vector<vector<mint>> c(n, vector<mint>(n));  
            REP(i, n) REP(j, n) REP(k, n) c[i][j] += a[i][k] * b[k][j];  
            return c;  
        };  
        vector<vector<mint>> a = {  
            {1, 2, 3},  
            {4, 5, 6},  
            {7, 8, 9}  
        }, d = {   // 単位行列  
            {1, 0, 0},  
            {0, 1, 0},  
            {0, 0, 1}  
        };  
        // a^10  
        binpow(a, 10, mul, d);  
    }  
  
    // 置換の積  
    {  
        const ll n = 3; // 置換の要素数  
        auto mul = [](vector<ll> a, vector<ll> b) {  
            vector<ll> ret(a.size());  
            REP(i, a.size()) ret[i] = b[a[i]];  
            return ret;  
        };  
        // (0, 2, 1) を 10回適用  
        binpow({0, 2, 1}, 10, mul, {0, 1, 2});  
    }  
}

このあいだのABCのD - Teleporterを置換の積と思うと、これで解ける
Submission #13117116 - AtCoder Beginner Contest 167

例題1
例題2

$x:=f(x)$ を繰り返す

$x \in T$ に関数 $f:T \to T$ を $K$ 回適用したときの値を計算する

$N=|T|$ と表す
$f(x)\ (x \in T)$ を $O(g)$ で計算可能なとき、前計算が $O(gN + N \log N)$ で可能
各クエリ $O(\log K)$ で計算可能

前計算

前計算では $\text{next} \lbrack k \rbrack \lbrack i \rbrack = (i$ 番目の要素の $2^k$ 個次の要素 $)$ を計算する
まず、 $\text{next} \lbrack 0 \rbrack \lbrack i \rbrack = g(x_i)$ で初期化する。 $k \gt =1$ に関しては $\text{next} \lbrack k \rbrack \lbrack i \rbrack = \text{next} \lbrack k-1 \rbrack \lbrack \text{next} \lbrack k-1 \rbrack \lbrack i \rbrack \rbrack$ と計算可能

クエリ

$x \in T$ に関数 $f:T \to T$ を $K$ 回適用したい
もし K&1<<i であったら $x = \text{next} \lbrack i \rbrack \lbrack x \rbrack$ として更新する

実装例

template<ll LOG=60>  
struct doubling {  
    // nxt[i][j] = (j番目の要素に関数fを2^i回適用した要素は何番目の要素か)  
    vector<vector<ll>> nxt;   
    doubling(vector<ll> nxt0) : nxt(LOG, vector<ll>(nxt0.size())) {  
        REP(i, nxt0.size()) nxt[0][i] = nxt0[i];  
        FOR(k, 1, LOG) REP(j, nxt0.size()) nxt[k][j] = nxt[k-1][nxt[k-1][j]];  
    }  
    // x番目の要素に関数fをk回適用した要素は何番目の要素か？  
    ll query(ll x, ll k) {  
        for(ll i=LOG-1; i>=0; --i) if(k&1LL<<i) x = nxt[i][x];  
        return x;  
    }  
};

この間のABCのD - Teleporterの場合、 $f(x) = a \lbrack x \rbrack$ とすればよい
Submission #13117497 - AtCoder Beginner Contest 167

合計・最小などの求解

前計算のタイミングで $2^k$ 回適用したところまでの合計、最小を求めておけばよい

試しに合計で考える
$\text{sum} \lbrack i \rbrack \lbrack j \rbrack = (j$ に $\lbrack 0, 2^i)$ 回適用した値の合計 $)$
$\text{sum} \lbrack i \rbrack \lbrack j \rbrack$ → $(j$ に $\lbrack 0,2^i)$ 回 $)$ → $(j$ に $\lbrack 0,2^{i-1})$ 回適用 $) + (\text{next} \lbrack i-1 \rbrack \lbrack j \rbrack$ に $\lbrack 0, 2^{i-1})$ 回適用 $)$
より小さい $i$ の情報を用いて計算できるので、 $i$ が小さい方から計算していける

二分探索

単調性があるなら二分探索できる

$x_i \leq x_{i+1}, x \leq f(x)$ みたいな単調性があるとする
$x$ から $y$ 以上に移動するのに必要な関数適用の回数の最小
$\text{next} \lbrack k \rbrack \lbrack a \rbrack \leq b$ が成り立つなら $ret += 2^k, a := \text{next} \lbrack k \rbrack \lbrack a \rbrack$ を $k$ が大きい方から実行すればよい