ABC156
修論の影響で生活習慣が後ろ倒しになっていて,晩御飯を食べ終えて部屋に戻ってきてツイッターを見て「そういえば今日ABCだったじゃん!(23時)」って気づくのが3回くらい続いていて,久しぶりの参加になってしまった.
解説PDF:今回のはやけに丁寧で勉強になる.
[C]までは問題なくできた.[C]は全探索に気づかなったので平均取ってN
で割ったのをint
に丸めて,それとそれを+1
したもので決勝戦をやる感じで書いた.計算量を見ましょう.
[D]
これがずっとできなくて終わってしまった.2^n mod 10^9+7
は,
L=10^9+7
,p
を2^p<=L
を満たす最大のp
として,そのp
を求める.n=cp+d
なるc,d
を求める.2^n=(2^d)*(2^p)^c
を計算する.
という方法でなんとか計算した(2^n
をn
についてのforで計算するとO(10^9)
になって間に合わないので,バッチを組むような感じ)けど二項係数がどうしても計算できなかった.
二項係数 (nCr) の計算方法:こうやって計算すれば良いらしい.フェルマーの小定理と繰り返し2乗法.
上で書いた2^n
の方法は計算量がlogになってないから,やっぱり繰り返し2乗法でやりましょうって感じ.
しかしこれはちょっとライブラリを作りたくなる気持ちもわかるなあという感じ…
他
まとまってて良さげだと思った記事:「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜