Codeforces Round #113 (Div. 2) E. Tetrahedron

Problem Statement – https://codeforces.com/problemset/problem/166/E

So we will use a DP with 2 states, that is at position D and A,B,C . Think why this optimal.

f[0][N] is the number of ways from D to D to using N steps

f[1][N] is the number of ways from A,B,C to D to using N steps

From D we can go to either A,B,C. Therefore,

f[0][N]=3∗f[1][N−1]

In order to calculate f[0][N] we need to calculate f[1][N]

From f[1][N] we could got to either at D or remaining 2 positions, Hence

f[1][N]=f[0][N−1]+2∗f[1][N−1]

So, we got to relations, i.e

f[0][N]=3∗f[1][N−1]

f[1][N]=f[0][N−1]+2∗f[1][N−1]

Base cases are

f[0][0]=1

f[1][0]=0

The Implementation is quite straight forward

#include <bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 1000000007
#define MAX 10000010
LL F[2][MAX];
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
void solve() {
    int n; cin >> n;
    F[0][0] = 1;
    F[0][1] = 0;
    for(int i=1; i<=n; i++) {
        F[0][i] = (3 * F[1][i-1])%MOD;
        F[1][i] = (F[0][i-1] + 2*F[1][i-1])%MOD; 
    }
    cout << F[0][n]%MOD << endl;
}
int main() {
    solve();
  __fastio;
  return 0;
}