PKU 3734-Blocks

PKU

問題概要

赤，緑，黄色，青のブロックをN個並べたい．
ただし，赤と緑は偶数個並べたい．
この時並べ方は何通りあるか．

解法

an 赤も緑も偶数個
bn 赤が奇数個
cn 緑が奇数個
dn 赤も緑も奇数個
とすると
a0=1
b0=0
c0=0
d0=0

an=an-1*2+bn-1+cn-1
bn=an-1+2*bn-1+dn-1
cn=an-1+2*cn-1+dn-1
dn=bn-1+cn-1+2*dn-1
が成り立つので繰り返し二乗法を用いる

実装(C++)

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef vector<int> Array;
typedef vector<Array> Matrix;
#define REP(i,x)for(int i=0;i<(int)x;i++)
const int MOD=10007;
Matrix operator*(const Matrix &a,const Matrix &b){
	int V=a.size();
	Matrix res(V,Array(V,0));
	REP(i,V){
		REP(j,V){
			REP(k,V){
				res[i][j]+=a[i][k]*b[k][j];
				res[i][j]%=MOD;
			}
		}
	}
	return res;
}
Matrix make_E(int V){
	Matrix res(V,Array(V,0));
	REP(i,V){
		res[i][i]=1;
	}
	return res;
}
Matrix operator^(const Matrix &a,int v){
	if(v==0)return make_E(a.size());
	Matrix res=(a*a)^(v/2);
	if(v&1)res=res*a;
	return res;
}
int main() {
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		Matrix base(4,Array(4));
		base[0][0]=2;
		base[0][1]=1;
		base[0][2]=1;
		base[0][3]=0;

		base[1][0]=1;
		base[1][1]=2;
		base[1][2]=0;
		base[1][3]=1;

		base[2][0]=1;
		base[2][1]=0;
		base[2][2]=2;
		base[2][3]=1;

		base[3][0]=0;
		base[3][1]=1;
		base[3][2]=1;
		base[3][3]=2;

		base=base^n;
		cout<<base[0][0]<<endl;
	}
	return 0;
}