競プロの記録 (2016_09_24)
今日は星１を６問と、星２を１問解いた。
そのほか中途半端な星２が１問。
「yukicoder: 星２」
愚直にやると10^(2+8)で間に合わない。
指数が小さいほうから計算していき、その都度一つ前のものを利用していけば、毎回丸々指数の分だけ計算する必要は無くなる。
これにより、10^2+10^8で間に合う。
自分はこのやり方で通したが、「繰り返し二乗法」と呼ばれるやり方があるらしい。
これでN乗の計算が、O(N)からO(logN)になる。
どうしても、ＭＯＤをとるのを忘れがちになるのを注意したい。
これは解けなかった。試合数は高々１５試合しかないので試す数は2^15 = O(10^4)となり、全探索することができる。
実装が長く、複雑になりそうなので、Ａ予選を控える今日はやらない。方針は立っているので、後日実装しようと思う。
Ａ予選まであと５分。
