AOJ 1327 : One-Dimensional Cellular Automaton

問題リンク：One-Dimensional Cellular Automaton | Aizu Online Judge

解法：
行列におとして計算した

N = 5 T = 1の場合、与えられた式を行列で表すと次の様になる

[ S(0,1) ]   [ S(-1,0) S(0,0) S(1,0) ] [A]
[ S(1,1) ]   [ S(0, 0) S(1,0) S(2,0) ] [ ]
[ S(2,1) ] = [ S(1, 0) S(2,0) S(3,0) ] [B]
[ S(3,1) ]   [ S(2, 0) S(3,0) S(4,0) ] [ ]
[ S(4,1) ]   [ S(3, 0) S(4,0) S(5,0) ] [C]

これを次の様に変える

[ S(0,1) ]   [ B C 0 0 0 ] [ S(0,0) ]
[ S(1,1) ]   [ A B C 0 0 ] [ S(1,0) ]
[ S(2,1) ] = [ 0 A B C 0 ] [ S(2,0) ]
[ S(3,1) ]   [ 0 0 A B C ] [ S(3,0) ]
[ S(4,1) ]   [ 0 0 0 A B ] [ S(4,0) ]


同様に、 N = 5 T = 2 の場合、

[ S(0,2) ]   [ S(-1,1) S(0,1) S(1,1) ] [A]
[ S(1,2) ]   [ S(0, 1) S(1,1) S(2,1) ] [ ]
[ S(2,2) ] = [ S(1, 1) S(2,1) S(3,1) ] [B]
[ S(3,2) ]   [ S(2, 1) S(3,1) S(4,1) ] [ ]
[ S(4,2) ]   [ S(3, 1) S(4,1) S(5,1) ] [C]

       |
       V

[ S(0,2) ]   [ B C 0 0 0 ] [ S(0,1) ]
[ S(1,2) ]   [ A B C 0 0 ] [ S(1,1) ]
[ S(2,2) ] = [ 0 A B C 0 ] [ S(2,1) ]
[ S(3,2) ]   [ 0 0 A B C ] [ S(3,1) ]
[ S(4,2) ]   [ 0 0 0 A B ] [ S(4,1) ]
    
       |
       V

[ S(0,2) ]   [ B C 0 0 0 ] [ B C 0 0 0 ] [ S(0,0) ]
[ S(1,2) ]   [ A B C 0 0 ] [ A B C 0 0 ] [ S(1,0) ]
[ S(2,2) ] = [ 0 A B C 0 ] [ 0 A B C 0 ] [ S(2,0) ]
[ S(3,2) ]   [ 0 0 A B C ] [ 0 0 A B C ] [ S(3,0) ]
[ S(4,2) ]   [ 0 0 0 A B ] [ 0 0 0 A B ] [ S(4,0) ]


といった風に求めたい行列S(0..N-1,T)はS(0..N-1,0)に
[ B C 0 0 0 ]
[ A B C 0 0 ]
[ 0 A B C 0 ]　のT乗を掛けたものになる
[ 0 0 A B C ]
[ 0 0 0 A B ] 

T乗をT回ループを回してやるとTLEになるので
繰り返し二乗法を使う

コード：

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vvi matrix;

int N,M,A,B,C,T;

void init(matrix &mat)
{

  mat[N-1][N-2]             = A;
  mat[0][0] = mat[N-1][N-1] = B;
  mat[0][1]                 = C;
  REP(i,1,N-1)
    {
      mat[i][i-1] = A;
      mat[i][i] = B;
      mat[i][i+1] = C;
    }
}

/*
pow,multiは行列のべき乗と掛け算
*/

int main()
{
  while(cin >> N >> M >> A >> B >> C >> T,N|M|A|B|C|T)
    {
      matrix s(N,vi(1));
      rep(i,N)cin >> s[i][0];
      matrix coef(N,vi(N,0));
      init(coef);
      coef = pow(coef,T);
      s = multi(coef,s);
      rep(i,N)cout << (i?" ":"") << s[i][0];
      cout << endl;
    }
  return 0;
}