Submission #1831737

---

Source Code Expand

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

long long memo[100000000];

long long trib(int n){
    
    if(memo[n]!=-1)return memo[n];
    
    if(n==1||n==2)return 0;
    
    else if(n==3)return 1;
    
    else
        return memo[n] = (trib(n-1) + trib(n-2) + trib(n-3))%10007;
        
    
}


int main(){
    long long n;
    cin >> n;
    for(int i=0;i<=1000000;i++)memo[i]=-1;
    cout << trib(n)%10007 << endl;
    
    return 0;
}

Submission Info

Judge Result