計算量O(N)をダブリングによってO(logN)にする D: 阿弥陀

問題

D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder

満点解法

D回だけループさせ阿弥陀をシュミレーションするという実装もできるがTLEとなる。 よってダブリングによって計算量を小さくする。

ダブリングとは

ダブリングを使ったべき乗計算はこちら。

keita-matsushita.hatenablog.com

これはX¹⁰を計算する時に10回ループを回して計算するのではなく。 X¹⁰ = X⁸ * X² として計算することでX^Nの時にO(logN)で計算できる。

これをこの問題に適用する。

なぜダブリングが使えるか。どう適用させるか。

ダブリングを実装方法

ダブリングは以下の手順で実装することができる。

阿弥陀くじの操作

今回の問題では、あみだくじのマップはA = {a1, a2, a3, a4, ..., ai, ... , am}で与えられる。これはそれぞれのaiに対してaiとai + 1のインデックスを交換することで阿弥陀の操作ができる。

ソースコード