SRM377 Div2 1000

とぷこだ 過去問

問題

無向グラフの隣接行列が与えられる。各頂点には、色(白か黒)と数字のマークが与えられている。
色が同じ頂点間には辺は存在しない。この無向グラフでゲームを行う。
ルールは、

  • 白と黒が交互にプレイする。最初は白。
  • 白のターンなら、各黒の頂点の隣接頂点のマークの和の値にその黒の頂点のマークの値を書き換える。白のマークの場所は変わらない。
  • 同様に黒のターンなら、各白の頂点の隣接頂点のマークの和の値にその白の頂点のマークの値を書き換える。

ということを繰り返す。N(10^9まで)ターン後のすべての頂点のマークの値を知りたい。
答えを10^9+7のmodで返す。

考え方

行列の累乗。
行列Aを、color[i]が'B'のとき、Aのi行はadjのi行と等しく、'W'のとき、Aのi行は単位行列のi行と等しいような行列とする。
行列Bを、color[i]が'W'のとき、Bのi行はadjのi行と等しく、'B'のとき、Aのi行は単位行列のi行と等しいような行列とする。
初期のマークの値をvとし、行列C=B*Aとすれば、
Nが偶数の時、C^(N/2)*vが答えになり、
Nが奇数の時は、A*C^(N/2)*vが答えになる。
この行列累乗C^mの計算は、繰り返し二乗法を用いてO(log m)で計算できる。

反省

蟻本p.181(行列累乗)を参考に。