Submission

PPPxxxxxxx

Score: 30

User: Jibhong

Problemset: Medulla

Language: cpp

Time: 0.009 second

Submitted On: 2024-12-13 19:47:53

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

// #define ll long long

// map <int,ll> mem;
// int fn[20020];

// ll func(ll x){
//     if(mem.count(x))return mem[x];
//     return mem[x] = ((func(x-3)*func(x-3)*func(x-3))%20011+(func(x-2)*func(x-1))%20011)%20011;
// }

// int main(){

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

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

//     fn[0]=0;
//     fn[1]=1;
//     fn[2]=8;

//     int n;
//     cin>>n;
//     // int last=3;
//     while(n--){
//         ll inp;
//         cin>>inp;
//     //     for(int i=last;i<=inp;++i){
//     //         if(fn[i%20011]){
//     //             mem[i]=fn[i%20011];
//     //         }else{
//     //             mem[i]=((mem[i-3]*mem[i-3]*mem[i-3])%20011+(mem[i-2]*mem[i-1])%20011)%20011;
//     //             fn[i%20011]=mem[i];
//     //         }
//     //     }
//     //     last=max(last,inp);
//     //     cout<<mem[inp]<<"\n";
//         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;
}