TopCoder SRM 377 Div1 Medium GameOnAGraph

TopCoder グラフ理論 行列

問題

頂点が黒または白のいずれかに塗られている無向グラフで次のようなゲームを行う。

  • 最初は白のターン
  • 白のターンのとき、黒の頂点にかかれている数字を、隣接する白の頂点にかかれている数字の和にする。白の頂点にかかれている数字はそのままにする。
  • 黒のターンのとき、白の頂点にかかれている数字を、隣接する黒の頂点にかかれている数字の和にする。黒の頂点にかかれている数字はそのままにする。


グラフおよび、初期状態での数字、それぞれの頂点の色が与えられているとき、
Nターンの操作を終えた後で、それぞれの頂点にかかれている数字をmod 10^9+7で求めよ。

制約条件

グラフの頂点≦50
初期状態での頂点の数字≦9

方針

それぞれのプレイヤーの操作は一つの行列として表せる。
Nターン後は(B*A)^N/2の操作の後、
Nが奇数ならさらにもう一度Aの操作をすると表せる。


行列の積を繰り返し二乗法により求めてやればよい。

ソースコード

const int mod=(int)1e9+7;
typedef vector<vi> mat;

mat operator*(mat &a,mat &b){
  mat c(a.size(),vi(b[0].size()));
  rep(i,c.size())rep(j,c[0].size())rep(k,a[0].size())
    (c[i][j]+=a[i][k]*b[k][j]%mod)%=mod;
  return c;
}
mat pow(mat m,int n){
  mat res(m.size(),vi(m.size()));
  rep(i,m.size())res[i][i]=1;
  for(;n;n/=2){
    if(n&1)res=m*res;
    m=m*m;
  }
  return res;
}

class GameOnAGraph {
  public:
  vector <int> getMarks(vector <string> adj, string colors, string marks, int N) {
    int n=adj.size();
    mat A(n,vi(n)), B(n,vi(n));
    rep(i,n)rep(j,n){
      if(colors[i]=='B'){
        B[i][j]=i==j;
        if(adj[i][j]=='1'&&colors[i]!=colors[j])A[i][j]=1;
      }
      else{
        A[i][j]=i==j;
        if(adj[i][j]=='1'&&colors[i]!=colors[j])B[i][j]=1;
      }
    }
    mat C=pow(B*A,N/2);
    if(N%2)C=A*C;
    mat tmp(n,vi(1));
    rep(i,n)tmp[i][0]=marks[i]-'0';
    tmp=C*tmp;
    vector<int> ans; rep(i,n)ans.pb(tmp[i][0]);
    return ans;
  }
};