Submission

PPPxxxxxxx

Score: 30

User: Jibhong

Problemset: Medulla

Language: cpp

Time: 0.453 second

Submitted On: 2024-12-13 19:40:57

#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;
}