SRM 377 Div1 Medium GameOnAGraph

問題

無向グラフが与えられる。各頂点は白か黒の色で塗られており、辺は異なる色の頂点間でのみ張られている。このグラフ上で次の手順でゲームを行う。

1. 白と黒が交互に行い、初手は白である。
2. 白のターンでは各黒の頂点にその頂点と隣接する白の頂点の点数を合計したものを代入する。この際、白の頂点の点数は変わらない。
3. 黒のターンでは各白の頂点にその頂点と隣接する黒の頂点の点数を合計したものを代入する。この際、黒の頂点の点数は変わらない。

これをNターン行う。

隣接行列がadjで与えられ、各頂点の色がcolors、点数の初期値がmarksで与えられる。このゲームを終えた後の各頂点の点数を1000000007で割ったあまりを返せ。

やりかた

SRM 376に続いて行列累乗。
頂点iが黒で頂点jが白でこのふたつが隣り合っているとした時、白のターンではとするような行列を、各頂点の点数をベクトルとして表現したものに掛け合わせることで、このターンを表現できる。

サンプルケース0)で考えてみると、1ターン目では頂点0に頂点1,2の点数を集める操作になり、これを行列で表現すると以下のようになる。

ただし、白のターンでは黒の頂点の点数は変わらないため、黒の頂点の部分の対角成分は1とし、点数がそのままになるようにする。黒のターンも同様のやりかたで行列で表現できる。
あとは白→黒→白→・・・とN回初期値に対してかければ良い。Nが大きいので繰り返し二乗法でやると良い。

以下ソース。

const ll MOD = 1000000007;

typedef vector<ll> vec;
typedef vector<vec> mat;

mat identity(ll n){
  mat E(n, vec(n, 0));
  for(ll i = 0; i < n; i++) E[i][i] = 1;
  return E;
}

mat mult(const mat &A, const mat &B){
  ll N = A.size(), M = B.size(), L = B[0].size();
  mat C(N, vec(L, 0));
  for(ll n = 0; n < N; n++)
    for(ll l = 0; l < L; l++)
      for(ll m = 0; m < M; m++)
	C[n][l] = (C[n][l] + A[n][m] * B[m][l]) % MOD;
  return C;
}

mat pow(const mat &A, ll p){
  mat R = identity(A.size());
  mat B = A;
  while(p){
    if(p & 1) R = mult(R, B);
    B = mult(B, B);
    p >>= 1;
  }
  return R;
}

class GameOnAGraph {
public:
  vector <int> getMarks(vector <string> adj, string colors, string marks, int N) {
    int L = adj.size();
    mat W(L, vec(L)), B(L, vec(L));
    
    for(int i = 0; i < L; i++){
      for(int j = 0; j < L; j++){
	if(colors[i] == 'W') B[i][j] = adj[i][j] == '1';
	if(colors[i] == 'B') W[i][j] = adj[i][j] == '1';
      }
      (colors[i] == 'B' ? B[i][i] : W[i][i]) = 1;
    }
    mat G = mult(B, W);
    G = pow(G, N / 2);
    if(N & 1) G = mult(W, G);

    mat v(L, vec(1));
    for(int i = 0; i < L; i++) v[i][0] = marks[i] - '0';
    mat ans = mult(G, v);

    vector<int> result;
    for(int i = 0; i < L; i++) result.push_back(ans[i][0] % MOD);
    return result;
  }
};