ABC008:D 高速累乗アルゴリズム

累乗を高速に計算する問題に感動したのでメモ。

問題:http://abc009.contest.atcoder.jp/tasks/abc009_4
解説:http://www.slideshare.net/chokudai/abc009 (pp.56-106)


(1)ナイーブな解き方

ghci> main
5 100
2345678901 1001001001 3333333333 3141592653 1234567890
2147483648 2147483647 4294967295 4294967294 3434343434
1067078691
(0.03 secs, 1519860 bytes)

ghci> main
30 999999999
11627 5078 8394 6412 10346 3086 3933 668 9879 11739 4501 6108 12336 8771 2768 2438 2153 7047 5476 313 1264 369 12070 10743 10663 747 370 4671 5235 3439
114 3613 3271 5032 11241 6961 3628 150 12191 2396 7638 3046 11594 8162 11136 786 9878 2356 11660 1070 3649 10882 9746 1415 3307 7077 9319 9981 3437 544
<interactive>: out of memory

(2) 高速累乗

ghci> main
5 100
2345678901 1001001001 3333333333 3141592653 1234567890
2147483648 2147483647 4294967295 4294967294 3434343434
1067078691
(0.00 secs, 1067548 bytes)

ghci> main
30 999999999
11627 5078 8394 6412 10346 3086 3933 668 9879 11739 4501 6108 12336 8771 2768 2438 2153 7047 5476 313 1264 369 12070 10743 10663 747 370 4671 5235 3439
114 3613 3271 5032 11241 6961 3628 150 12191 2396 7638 3046 11594 8162 11136 786 9878 2356 11660 1070 3649 10882 9746 1415 3307 7077 9319 9981 3437 544
2148
(0.30 secs, 158523952 bytes)


問題に付いている入力例3の計算量の違いを見てみると、
(1)ナイーブ
O(n^3 * m)

ghci> 30^3 * (999999999 - 30)
26999999163000

2.7e+13


(2)高速
O(n^3 * lb m)

ghci> 30^3 * (logBase 2 $ 999999999 - 30)
807228.5258500932

8.1e+5


計算量は解説105ページに書かれています。
とんでもない違いが出るのですね。実感しました。


#背景が黒だとtex記法が見えないのかな?