tarunon

[A0,A1]×[[X,Y],[Z,W]]=[A1,A2]となる行列XYZWを求める。この時、mod100は最終項の下2桁を取れば良いので無視する。A2=A0+A1のとき、行列は[[0,1],[1,1]]なので、答えは([A0,A1]×[[0,1],[1,1]]^N)[0]%100となる。計算量はO(logN) (edited)

これ対角化すれば行列の累乗計算いらないですね。 pow((1-sqrt(5))/2, N) が出てきますがこれって計算量どうなるんですっけ