Tetreahedron Problem (O(n) and O(log(n)) solution

#	User	Rating
1	tourist	3985
2	jiangly	3885
3	jqdai0815	3682
4	Benq	3580
5	orzdevinwang	3526
6	ksun48	3506
7	ecnerwala	3505
8	Radewoosh	3457
9	Kevin114514	3377
10	gamegame	3374

#	User	Contrib.
1	cry	170
2	Um_nik	162
3	atcoder_official	161
4	maomao90	159
5	-is-this-fft-	158
6	djm03178	157
7	Dominater069	156
8	adamant	154
9	luogu_official	153
10	awoo	152

Link to the problem You are given a tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (1e9 + 7).

Idea is simple,

Base case?

For a general i?

Think a little bit (relation between A, B and C)

Use the above mentioned recursive relations to find out the answer

Code

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> fD(n + 1), fA(n + 1);
    fD[0] = 1;
    fA[0] = 0;

    for (int i = 1; i <= n; ++i) {
        fD[i] = (3 * fA[i - 1]) % MOD;
        fA[i] = (2 * fA[i - 1] + fD[i - 1]) % MOD;
    }

    cout << fD[n] << endl;
    return 0;
}

Optimized code can be found here (DP solution Click here for code)

What if n<= 1e18? Think about the optimizing the above equations in matrix form, u might have done this for fibonacci series

Further optimized code (Click here for code)

Solutions are discussed in this video

extruder's blog