ABC156_D - Bouquet

abc156はC問題まですぐにできたけど、Dにずっと引っかかってしまった・・・回答を見てもわけがわからないので、わからない要素を分解していく。

繰り返し二乗法

繰り返し二乗法というのも重要なトピックである。この記事が一番わかりやすかった。

累乗は、愚直に計算すれば計算数はO(n)となるが、これをO(logN)まで抑えることができる。 logってなんだ・・・

log

でもその前に対数について ”aを何乗したらbになるか”を表す数として定義される。

例えば、最もかんたんなlognとなるアルゴリズムは、下記の様なものになる。

for (int i = 1; i <= n; i = i * 2) { // nは入力サイズとする  
    count++; // logn回実行
}

まだざっくりとしかわかってないけど、要は繰り返すたびに計算量がガンガン減っていくものはこれに当てはまりそう。バイナリサーチは、「繰り返しのたびに問題のサイズが２分の１になる」ため、計算量は O(log⁡n) になる。

繰り返し二乗法は、ようは累乗の指数をグループ化していって計算量を減らしてしまうということ。下記のようなイメージ。

具体的なコードは下記。

func repSquare(n, p int) int {  
    if p == 0 {
        return 1
    }
    if p%2 == 0 {
        t := repSquare(n, p/2)
        return t * t % m
    }
    return n * repSquare(n, p-1) % m
}

剰余演算

(10^9+7)で割った余りを求めてください。という文言は決り文句らしい。まず前提として、余りを取りたいときは、いつ余りをとっても計算結果はかわらないから、何回あまりをとってもOKということ。
気をつけないと行けないのは、マイナスが付くとおかしくなるので、あまりを求めた結果が負になったら法 1000000007 を足すということ。

これに関しても基本ライブラリを作っておくものらしいが、一旦はここまでの理解でおいておく。

nCr

n個のうちからr個を選ぶ、というときに利用される公式であって、
となる。

とすると、下記のアルゴリズムでいいんじゃね？となるけど、これだとすぐに桁あふれを起こす。

func comb(n, c int) int {  
    mod := 1000000007
    nc := n
    nr := 1
    for i := 0; i < c; i++ {
        nc *= n - 1
        nr *= (i + 1)
    }
    return (nc / nr) % mod
}

だからって、途中でmodで割ると計算が合わない。

modと≡について

例えばmで余りを取ることをmでmodを取るなどという。そして≡は懐かしき合同を意味する。で、modの世界では1≡59 (mod 28)みたいに余りが同じであればこれらは合同であるとする。ここに色々法則があるみたいで、今回の問題もそれらを理解していないとできない。基礎的な法則はここにまとまっている。

この法則を使うと、9÷4≡12(mod 13)とすることができる。(両辺に4をかければ良い。)

逆元

a / b(mod p)を計算する方法を考えてみる。実はこれは、1 / b (mod p)が計算できれば良いということになる。なぜか。
上記の用に、modの合同においては両辺を何倍しても良いので、a / b ≡ a * (1 / b) mod pが成り立つからだ。
なので、1 / bを計算して、これをa倍すれば良い。そして、このような 1 / b を逆元と呼ぶ。
b をかけると 1 になる数とも言える。

1 / bはb^-1なので、 a / b ≡ a * b^-1(mod p)である。割り算がなくなった！だけど、指数^-1は結局割り算なので、これをなくすために、かんたんな方法としてフェルマーの小定理がある。

フェルマーの小定理

pを素数、aをpの倍数でない整数としてa^(p−1)≡1(mod p)が成立するというもの。ようはよく出る10^9+7のやつにはこれを適用すれば割り算をなくして、a^(p−2)(mod p)が逆元となっているので、これを計算すればいい。

回答

func comb(n, k int) int {  
    if k < 1 || k > n {
        return 0
    }
    nu, de := 1, 1
    for i := 0; i < k; i++ {
        nu = nu * (n - i) % m
        de = de * (i + 1) % m
    }
    return nu * repSquare(de, m-2) % m
}

func repSquare(n, p int) int {  
    if p == 0 {
        return 1
    }
    if p%2 == 0 {
        t := repSquare(n, p/2)
        return t * t % m
    }
    return n * repSquare(n, p-1) % m
}

func main() {  
    var n, a, b int
    fmt.Scan(&n, &a, &b)

    all := repSquare(2, n)

    ca := comb(n, a)
    cb := comb(n, b)
    ans := all - 1 - (ca + cb)

    ans = (ans%m + m) % m // negative mod -> positive mod
    fmt.Println(ans)
}

こうしてみると一つの問題でわからないトピックが３つもある。。。しかも解説を見てもはーなるほどね、とならない。

Menu

繰り返し二乗法

log

剰余演算

nCr

modと≡について

逆元

フェルマーの小定理

回答