Painting-Fence (DP)

long long countWays(int n, int k){
// dp[i][j][k] -> number of ways from first i elements
// where ith color is j and there are k consecutive elements of color j
// dp[i][j][2] = dp[i-1][j][1]
// dp[i][j][1] = sigma_{x!=j} dp[i-1][x][{1,2}]
int dp[n+1][k+1][3];
memset(dp,0,sizeof(dp));
for(int i=1;i<=k;i++) dp[1][i][1] = 1;
for(int i=2;i<=n;i++){
    ll s= 0 ;
    for(int j=1;j<=k;j++){
        add_self(s,dp[i-1][j][1]);
        add_self(s, dp[i-1][j][2]);
    }
    for(int j=1;j<=k;j++){
        ll x = s;
        dp[i][j][2] =  dp[i-1][j][1];
        sub_self(x, dp[i-1][j][1]);
        sub_self(x,dp[i-1][j][2]);
        dp[i][j][1]=x;
    }
}
ll ans=0;
for(int i=0;i<=k;i++) {
    for(int j=0;j<=2;j++)
        add_self(ans,dp[n][i][j]);
}
return ans;
    }