1 /* 1438 */ 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5  6 #define MAXN 32 7  8 const int MAXS = 1<<4; 9 10 __int64 dp[MAXN][MAXS][4][2];11 int cnt[1<<4];12 13 int abs(int x) {14     return x<0 ? -x:x;15 }16 17 int main() {18     int i, j, k, n;19     int s;20     __int64 ans;21     22     memset(cnt, 0, sizeof(cnt));23     for (i=0; i<MAXS; ++i)24         for (j=0; j<4; ++j)25             if (i & (1<<j))26                 ++cnt[i];27     28     memset(dp, 0, sizeof(dp));29     for (i=0; i<4; ++i)30         dp[1][1<<i][i][0] = 1;31         32     for (n=2; n<MAXN; ++n) {33         for (i=0; i<MAXS; ++i) {34             for (j=0; j<4; ++j) {35                 for (k=0; k<4; ++k) {36                     s = i | (1<<j);37                     dp[n][s][j][1] += dp[n-1][i][k][1];38                     if (abs(j-k) == 3) {39                         dp[n][s][j][1] += dp[n-1][i][k][0];40                     } else {41                         dp[n][s][j][0] += dp[n-1][i][k][0];42                     }43                 }44             }45         }46     }47     48     for (n=2; n<MAXN; ++n) {49         ans = 0;50         for (i=0; i<MAXS; ++i) {51             if (cnt[i] >= 3)52                 ans += dp[n][i][0][1] + dp[n][i][1][1] +53                      dp[n][i][2][1] + dp[n][i][3][1];54         }55         printf("N=%d: %I64d\n", n, ans);56     }57     58     return 0;59 }