繰り返し二乗法に関する頭の整理 - どこにでもいるSEの備忘録

$2 ^{10000000}$ みたいなのを高速に計算しようと思ったときに、繰り返し二乗法というテクニックがあります。今回は、繰り返し二乗法の中身について頭の整理のメモです。

繰り返し二乗法
例題
感想

繰り返し二乗法

繰り返し二乗法は、 $2 ^{10000000}$ みたいな値を高速に計算するテクニックです。

アイデアとしては、

$2^2 = 2^1 \cdot 2^1$

$2^4 = 2^2 \cdot 2^2$

$2^8 = 2^4 \cdot 2^4$

$2^{16} = 2^8 \cdot 2^8$

$2^{32} = 2^{16} \cdot 2^{16}$

のように、指数が2のべき乗になっている時、指数/2したものを二乗することで計算します。こうすることで、単純に指数回だけ2を掛けるより高速に結果を求めることができます。

$a^{n}$ をGoの関数で書くと、こんな感じになります。

func pow(a int, n int) int {
    if n == 1 {
        return a
    }
    if n%2 == 1 {
        return a * pow(a, n-1)
    }
    ret := pow(a, n/2)
    ret = (ret * ret)

    return ret
}

書いてみると意外とシンプルですが、これが結構高速化に役立ちます。

例題

atcoder.jp

解説を見るとフェルマーの小定理を使った式変形とか、1000000007の余りをとったりと、若干（？）他にもポイントはありますが、その辺すっ飛ばしてやってみます。

package main

import (
    "fmt"
)

func main() {
    var n, a, b int
    fmt.Scanf("%d %d %d", &n, &a, &b)

    mod := int(1e9) + 7

    ans := (powMod(2, n, mod) - 1 - nCrMod(n, a, mod) - nCrMod(n, b, mod)) % mod
    if ans < 0 {
        ans += mod
    }
    fmt.Println(ans)
}

func powMod(a int, n int, b int) int {
    if n == 1 {
        return a
    }
    if n%2 == 1 {
        return a * powMod(a, n-1, b) % b
    }
    ret := powMod(a, n/2, b)
    ret = (ret * ret) % b

    return ret
}

func nCrMod(n int, r int, mod int) int {
    ret := 1
    //X
    for i := n - r + 1; i <= n; i++ {
        ret *= i
        ret %= mod
    }
    //Y
    for i := 2; i <= r; i++ {
        ret *= powMod(i, mod-2, mod)
        ret %= mod
    }
    ret %= mod
    if ret < 0 {
        ret += mod
    }
    return ret
}