Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <iostream>
#include <vector>

using namespace std;

const int N = (int) 1e5 + 5;
const int MOD = (int) 1e9;

int a[N];
int n;

int main() {
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> p;
    for (int i = 1;;) {
        p.push_back(i * (3 * i - 1) / 2);
        if (p.back() >= n) break;
        i = -i;
        if (i > 0) i++;
    }

    a[0] = 1;
    for (int i = 1; i <= n; ++i) {
        int sign = 1, cnt = 0;
        for (int j : p) {
            if (j > i) break;
            a[i] += sign * a[i - j];
            if (a[i] < 0) a[i] += MOD;
            if (a[i] >= MOD) a[i] -= MOD;
            cnt += 1;
            if (cnt == 2) {
                cnt = 0;
                sign = -sign;
            }
        }
    }

    cout << a[n] << endl;
    return 0;
}

Code mẫu của RR

#include<bits/stdc++.h>

using namespace std;

#define MOD 1000000000

int A[350][100010];
int n;
int B[101000];
//A[x][n] --> so cach bieu dien x thanh tong n so;

int main() {

    scanf("%d", &n);

    int sq = sqrt(n) + 1;

    for (int i=1; i<=n; i++) {
        A[1][i] = 1;
        A[2][i] = (i/2);
    } // base case

    for (int i=3; i<=sq; i++) {
        for (int j=i; j<=n; j++) {
            A[i][j] = (A[i-1][j-1] + A[i][j-i]);
            if (A[i][j] >= MOD) A[i][j] -= MOD;
        }
    }   

    // start at column sq + 1;
    int minS = sq + 1;

    // tinh (n + 1, 1) --> (n + sq + 1, 1 + sq)

    for (int i = minS; i <= n + sq; i++) {
        // bieu dien i thanh j so
        int u = 1;
        int v = i - minS + 1;
        while (v > 0) {
            B[i] += A[u][v];
            u++;
            v -= (minS-1);
            if (B[i] >= MOD) B[i] -= MOD;
        } 
    }

    for (int i = minS - 1; i >= 1; i--) {
        B[i] = 1;
        for (int j = i; j <= n; j++) {
            B[j] += B[j-i];
            if (B[j] >= MOD) B[j] -= MOD;
        }
    }

    printf("%d", B[n]);
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long n,dd,i,j,jj,np[602];
long long l[100012];
main()
{
scanf("%ld",&n);
if(n==0) printf("0");
else
  {
  np[0]=0;
  dd=1;i=0;
  while(np[i]<=n)
    {
    i=i+1;
    jj=(i+1)/2*dd;
    dd=-dd;
    np[i]=jj*(3*jj-1)/2;
    }
  l[0]=1;
  l[1]=1;
  for(long i=2;i<=n;i++)
    {
    j=1;
    while(np[j]<=i)
      {
      if(j%4==0||j%4==3)
        l[i]=l[i]+1000000000-l[i-np[j]];
      else
        l[i]=l[i]+l[i-np[j]];
      j=j+1;
      }
    l[i]=l[i]%1000000000;
    }
  printf("%lld",l[n]);
  }
//getch(); 
}

Code mẫu của khuc_tuan

#include "iostream"
#include "fstream"
#include "stdlib.h"

using namespace std;

#define MOD 1000000000

int n, sign;
int f[100010];
int res;

int main() {

    scanf("%d",&n);

    f[0] = 1;
    f[1] = 1;

    for(int i=2;i<=n;++i) {
        res = 0;
        sign = 1;
        for(int t=1;;++t) {
            int k = t*(3*t-1)/2;
            if(k>i) break;
            res = (res+sign*f[i-k])%MOD;
            if(res<0) res+=MOD;
            k += t;
            if(k>i) break;
            res = (res+sign*f[i-k])%MOD;
            if(res<0) res+=MOD;
            sign = -sign;
        }
        f[i] = res;
    }
    if(n==0) cout << 0 << endl; else cout << f[n] << endl;
    return 0;
}