Submission #4042478

---

Source Code Expand

#include <iostream>
using namespace std;

long long a[1000010] = {0};

long long func(int n) {
  if (n == 1 || n == 2) {
    return 0;
  }
  if (n == 3) {
    return 1;
  }

  if (a[n] > 0) {
    return a[n];
  }

  a[n] = (func(n-1) + func(n-2) + func(n-3)) % 10007;
  return a[n];
}

int main() {
  int n;

  cin >> n;

  a[1] = 0;
  a[2] = 0;
  a[3] = 1;

  long long ans = func(n);

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result