Top Secret (UVa Live Archive Europe Southwestern 2008)
問題
円環の中に長さNの数列がある。この数列の各数値に対して自分自身と左側のL倍と右側のR倍を足した数値を新しい数値にするという操作をS回繰り返す。下X桁だけ取り出した最終的な数列を答えよ。
2<=N<=1,000
0<=S<=2^30
0
解法
行列を作ってS乗する。この時、行列は巡回行列になっているので、掛け算をする時に1行目だけ求めて、残りは1行目をずらした物を入れるとO(N^2logS)で計算できる。
