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; }