Ways to color a 3xN Board
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| long long dp[101010][4][4][4];
const long long mod = 1e9 + 7;
long long helper(int A, int p, int mask1, int mask2, int mask3) {
if(p == A) return 1;
if(dp[p][mask1][mask2][mask3] != -1) return dp[p][mask1][mask2][mask3];
long long& res = dp[p][mask1][mask2][mask3] = 0;
for(int i = 0; i < 4; i++) {
if(i == mask1) continue;
for(int j = 0; j < 4; j++) {
if(j == mask2) continue;
for(int k = 0; k < 4; k++) {
if(k == mask3) continue;
if(i == j) continue;
if(j == k) continue;
res = (res + helper(A,p + 1,i,j,k)) % mod;
}
}
}
return res;
}
int Solution::solve(int A) {
memset(dp, -1, sizeof dp);
long long res = 0;
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
for(int k = 0; k < 4; k++) {
if(i == j) continue;
if(j == k) continue;
res = (res + helper(A - 1,0,i,j,k)) % mod;
}
}
}
return res;
}
|
