Submission

PPPPPPPPPP

Score: 100

User: Jibhong

Problemset: Medulla

Language: cpp

Time: 1.866 second

Submitted On: 2024-12-13 20:08:58

#include <bits/stdc++.h>
using namespace std;

#define ll long long

vector <ll> mem (7500010,-1);

ll last=3;

ll func(ll x){
    if(mem[x]!=-1)return mem[x];
    for(;last<=x;++last){
        mem[last] = ((mem[last-3]*mem[last-3]*mem[last-3])+(mem[last-2]*mem[last-1]))%20011;
    }
    if(last>x)--last;
    return mem[x];
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    mem[0]=0;
    mem[1]=1;
    mem[2]=8;


    int n;
    cin>>n;
    while(n--){
        ll inp;
        cin>>inp;
        cout<<func(inp)<<"\n";
    }

    return 0;
}


// #include <bits/stdc++.h>
// using namespace std;

// #define ll long long
// const int MOD = 20011;

// vector<ll> mem(20020, -1); // Preallocate memory

// // Bottom-up approach to compute f(x)
// ll func(ll x) {
//     if (x <= 2) return x * x * x; // Base cases
//     if (mem[x] != -1) return mem[x]; // Return if already computed
    
//     // Compute values iteratively
//     for (ll i = 3; i <= x; ++i) {
//         if (mem[i] == -1) {
//             mem[i] = ((mem[i - 3] * mem[i - 3] % MOD * mem[i - 3] % MOD) % MOD +
//                       (mem[i - 2] * mem[i - 1]) % MOD) % MOD;
//         }
//     }
//     return mem[x];
// }

// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0);

//     // Base cases
//     mem[0] = 0;
//     mem[1] = 1;
//     mem[2] = 8;

//     int n;
//     cin >> n;
//     while (n--) {
//         ll inp;
//         cin >> inp;
//         cout << func(inp) << "\n";
//     }

//     return 0;
// }