PKU 2440 DNA

http://poj.org/problem?id=2440
0と1をL個並べたときに、101という並びと111という並びを含まない並びの個数を2005で割った余りを求めろと言うな問題。

上手くやれば繰り返し二乗法は必要ないようです。
漸化式を作って動的計画法。周期は200？

vector<vector<int> > mult(const vector<vector<int> >& le,const vector<vector<int> >& ri){
  vector<vector<int> > ret(8,vector<int>(8,0));
  rep(i,8){
    rep(j,8)rep(k,8)ret[i][j]=(ret[i][j]+le[i][k]*ri[k][j])%2005;
  }
  return ret;
}

vector<vector<int> > mat(8,vector<int>(8,0));

vector<vector<int> > pow(int n){
  if(n==0){
    vector<vector<int> > ret(8,vector<int>(8,0));      
    rep(i,8)ret[i][i]=1;
    return ret;
  }
  vector<vector<int> > ret=pow(n/2);
  ret=mult(ret,ret);
  if(n%2)ret=mult(ret,mat);
  return ret;
}

main(){
  rep(i,8)mat[i][i/2]=mat[i][i/2+4]=1;
  mat[2][5]=mat[3][5]=mat[6][7]=mat[7][7]=0;
  int n;
  while(cin>>n){
    vector<vector<int> >ansm=pow(n%200);
    int ans=0;
    rep(i,8)ans+=ansm[0][i];
    ans-=ansm[0][5]+ansm[0][7];
    cout<<ans%2005<<endl;
  }
}