Lick the dog till the last one has nothing (linear DP)

Lick the dog and lick until the last thing is nothing

Thank you, blogger :https://blog.csdn.net/qq_51282224/article/details/122638737
link ：https://ac.nowcoder.com/acm/contest/24213/1002

Title Description
As the core of the team ,forever97 He is respected by the other two teammates .
Trote_w Please... Every day forever97 Take out , But unfortunately, the center of the universe forever97 There are only 3 home forever97 Favorite takeout .
If Trote_w to forever97 Bought takeout from another family ,forever97 Will shout “ I don't eat I don't eat ”.
however forever97 I don't like to eat a takeout for three days in a row .
If Trote_w One day I forgot about it and bought him the same takeout for three days , that forever97 It will Trote_w Press your head into the screen of your mobile phone .
As Trote_w Good friends , You can tell him to keep asking forever97 eat n Tianfan , How many different ways to buy ？

Input description :
Multiple sets of samples
The first line is an integer T(1<=T<=20) Represents the number of test samples
Next t Each row is an integer n, representative Trote_w Please forever97 eat n Tianfan (1<=n<=100000)

Output description :
Output T An integer represents the number of schemes , Because the answer is too big , You just need to output mod 1e9+7 The answer after .
Example 1
Input

2
3
500

Output

24
544984352

dp Ideas

Because the topic requires not to go to the same house for three consecutive days , So we just need to think about the i-1 Days and i-2 Days are enough

State means ：
f[0/1/2][i] front i Day to day 0/1/2 Home buying program

State calculation
f[0][i]=f[1][i-1]+f[2][i-1]+f[1][i-2]+f[2][i-2]

f[1][i]=f[0][i-1]+f[2][i-1]+f[0][i-2]+f[2][i-2]

f[2][i]=f[1][i-1]+f[0][i-1]+f[1][i-2]+f[0][i-2]

Then observe and find i - 1 Days and i - 2 The method of days has been used twice , So it turns into one dimension

A two-dimensional dp

#include <iostream>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
ll f[3][maxn];
int t, n;

int main(){
    cin >> t;
    while(t --){
        cin >> n;
        f[0][0] = f[1][0] = f[2][0] = 0;
        f[0][1] = f[1][1] = f[2][1] = 1;
        f[0][2] = f[1][2] = f[2][2] = 3;
        for(int i = 3;i <= n;i ++){
            f[0][i]=(f[1][i-1]+f[2][i-1]+f[1][i-2]+f[2][i-2])%mod;
            f[1][i]=(f[0][i-1]+f[2][i-1]+f[0][i-2]+f[2][i-2])%mod;
            f[2][i]=(f[1][i-1]+f[0][i-1]+f[1][i-2]+f[0][i-2])%mod;
        }
        cout << (f[0][n]%mod+f[1][n]%mod+f[2][n]%mod)%mod << endl;
    }
    return 0;
}

A one-dimensional dp

#include <iostream>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
ll f[maxn];
int t, n;

int main(){
    cin >> t;
    while(t --){
        cin >> n;
        f[0] = 0;
        f[1] = 3;
        f[2] = 9;
        for(int i = 3;i <= n;i ++){
            f[i] = (f[i - 1] * 2 + f[i - 2] * 2) % mod;
        }
        cout << f[n] << endl;
    }
    return 0;
}