首先，这道题可以用DP取得80分的部分分（完全背包问题，把1~n的数视为物品）
关于优化，请参考 【提高版】DP知识笔记2 中的完全背包部分

80分 C++代码

    opt[0] = 1;
    for(Re int i = 1;i <= n;i++){
        for(Re int j = i;j <= n;j++){
            opt[j] += opt[j - i];
            opt[j] %= mod;
        }
    }
    cout << opt[n] << endl;

但是$O(n^2)$显然不能满足题目的数据范围（$n\leq100000$）
那么，根据常识，正解时间复杂度约为$O(n\log n)$或$O(n\sqrt{n})$
母函数：
对于一个问题，方案数为$P_0,P_1,P_2,\dots,P_n$（该序列记成${P_n}$）
则该数列的生成函数为：$f(x)=P_0x^0+P_1x^1+P_2x^2+\dots+P_nx^n$（把每一项看成系数）
也可化成：$\quad\quad\quad\quad\quad f(x)=(1+x+x^2+x^3+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots$
重点：选第二个式子括号里的项表示$P_n$，在第$k$个括号选第$i$个项，表示数字$k$选择$i - 1$个
这样就可以构造出母函数的两种情况了。
把第二个式子化简可得：
$\quad f(x)=(1+x+x^2+x^3+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots (0\leq x<1)$
$=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}\dots$
$=\frac{1}{(1-x)(1-x^2)\dots}$
$=\frac{1}{1-x-x^2+x^5+x^7-x^{12}\dots}$（指数规律：$\frac{3k^2\pm k}{2}$）
$∴f(x)(1-x-x^2+x^5+x^7-x^{12}\dots)=1$
综上可得：
$(P_0x^0+P_1x^1+P_2x^2+\dots+P_nx^n)(1-x-x^2+x^5+x^7-x^{12}\dots)=1$
$x^n$的系数：
$P_n-P_{n-1}-P_{n-2}+P_{n-5}+P_{n-7}\dots=0$
$∴P_n=P_{n-1}+P_{n-2}-P_{n-5}-P_{n-7}\dots$（减数规律：$\frac{3k^2\pm k}{2}$）（项数：$O(\sqrt {n})$）

于是，$P_n=P_{n-1}+P_{n-2}-P_{n-5}-P_{n-7}\dots$也就成了我们的状态转移方程。
算法总时间复杂度：$O(n\sqrt{n})$

100分 C++ 代码

#include<iostream>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define ll long long
int n,ans,mod;
ll p[MAXN];
int main() {
    cin >> n >> mod;
    p[0] = 1;
    for(Re int i = 1;i <= n;i++){
        int s = 1;
        for(re ll k = 1;k <= n;k++){
            ll c1 = (3 * k * k - k) / 2;
            ll c2 = (3 * k * k + k) / 2;//这里用long long是因为3 * k * k可能超过int类型的存储范围。
            if(c1 <= i)p[i] += s * p[i - c1];
            if(c2 <= i)p[i] += s * p[i - c2];
            if(c1 > i || c2 > i)break;//边界限制
            s *= -1;
            p[i] %= mod;
        }
        p[i] %= mod;
        if(p[i] < 0)p[i] += mod;//防止p[i]小于0
    }
    cout << p[n] << endl;
    return 0;
}

相关链接：

yxc老师的视频讲解：https://www.acwing.com/video/854/
数学知识笔记：https://www.acwing.com/blog/content/1622/
【提高版】DP知识笔记2：https://www.acwing.com/blog/content/1673/