PKU 3734 Blocks

http://poj.org/problem?id=3734
n個に並べた直線状のブロックの色の塗り方を数える問題。
ただし、色は4色あり、赤と緑は偶数個でないといけない。

漸化式をたてて、繰り返し二乗法を用いる。
n個並べたときに、赤と緑が偶数個ある組み合わせの数をee_nとし、赤と緑が奇数この組み合わせの数をoo_nとして、それ以外をeo_nとすると



というような漸化式が立てられるので、行列の掛け算に直しました。

typedef vector<int> vi;
typedef vector<vi> mat;

mat operator*(const mat&l,const mat&r){
  mat ret(SZ(l),vi(SZ(r[0])));
  rep(i,SZ(l)){
    rep(j,SZ(r[0])){
      ret[i][j]=0;
      rep(k,SZ(l[0]))ret[i][j]=(ret[i][j]+l[i][k]*r[k][j])%10007;
    }
  }
  return ret;
}

mat ki;

mat pow(const mat&in,int p){
  mat ret;
  if(p==1)return ki;
  if(p%2){
    mat tt=pow(in,p/2);
    ret=ki*tt*tt;
  }else{
    mat tt=pow(in,p/2);
    ret=tt*tt;
  }
  return ret;
}

main(){
  int test;
  cin>>test;
  int a[3][3]={{2,1,0},
              {2,2,2},
              {0,1,2}};
  ki.resize(3);
  ki[0].assign(a[0],a[0]+3);
  ki[1].assign(a[1],a[1]+3);
  ki[2].assign(a[2],a[2]+3);
  
  while(test--){
    ll n;
    cin>>n;
    mat ans=pow(ki,n);
    cout<<ans[0][0]%10007<<endl;
  }
}