SRM 412 D1 250 ForbiddenStrings

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)


class ForbiddenStrings {
public:
    long long countNotForbidden(int n) {
        if(n==1) return 3;
        vector<vector<vector<LL> > > dp(30,vector<vector<LL> > (3,vector<LL>(3)));
        REP(i,3)
        REP(j,3)
        {
            dp[0][i][j]=1;
        }
        REP(i,29)
        REP(j,3)
        REP(k,3)
        {
            if(j==k)
                dp[i+1][j][k]+=dp[i][0][j]+dp[i][1][j]+dp[i][2][j];
            else
                dp[i+1][j][k]+=dp[i][j][j]+dp[i][k][j];
        }

        LL res=0;
        REP(i,3)
        REP(j,3)
            res+=dp[n-2][i][j];
        return res;
    }

};