CFR 166 E. Tetrahedron ( DP )

Problem - 166E - Codeforces
題意：
在一個四角錐上，求有多少路徑可以恰好 N 步從起點返回到起點。
解法：
dp[ i ][ j ] : 考慮前 i 個步，最後在 j 號點時的方法數
dp[ i ][ j ] = SIGMA{ dp[ i - 1 ][ k ] | k ≠ j }

int N;

void init(){
	cin >> N;
}

vvi dp;
int t;

void preprocess(){
	dp = vvi( 2, vi( 4 ) );
	dp[ t ][ 0 ] = 1;
	for( int i = 0; i < N; ++i, fill( dp[ t ].begin(), dp[ t ].end(), 0 ), t ^= 1 )
		for( int j = 0; j < 4; ++j )
			for( int k = 0; k < 4; ++k )
				if( j != k )
					( dp[ t ^ 1 ][ k ] += dp[ t ][ j ] ) %= MOD7;
}

void solve(){
	cout << dp[ t ][ 0 ] << endl;
}