这题费了我好长时间才调出来……

一直80：

#include<iostream>
#include<cmath>
using namespace std;
long long f[100005],g[350][100005];
long long k[100005];
int main()
{
    int n,p;
    long long ans=0;
    cin>>n>>p;
    int m=sqrt(n);
    f[0]=1;
    for(int i=1;i<=m;i++)for(int j=i;j<=n;j++)
    {f[j]+=f[j-i];f[j]%=p;}
            g[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=i;j<=n;j++)
        {
            g[i][j]=g[i][j-i];
            if(j>m)g[i][j]+=g[i-1][j-m-1];
            g[i][j]%=p;
        }
    }
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)k[j]+=g[i][j];
    }
    for(int i=0;i<=n;i++)
    {
        ans+=f[i]*k[n-i];
        ans%=p;
    }
    cout<<ans<<endl;
    return 0;
}

so?

100：

#include<iostream>
#include<cmath>
using namespace std;
long long f[100005],g[350][100005];
long long k[100005];
int main()
{
    int n,p;
    long long ans=0;
    cin>>n>>p;
    int m=sqrt(n);
    f[0]=1;
    for(int i=1;i<=m;i++)for(int j=i;j<=n;j++)
    {f[j]+=f[j-i];f[j]%=p;}
    g[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=i;j<=n;j++)
        {
            g[i][j]=g[i][j-i];
            if(j>m)g[i][j]+=g[i-1][j-m-1];
            g[i][j]%=p;
        }
    }
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)k[j]+=g[i][j],k[j]%=p;
    }
    for(int i=0;i<=n;i++)
    {
        ans+=f[i]*k[n-i];
        ans%=p;
    }
    cout<<ans<<endl;
    return 0;
}

（看出区别了吗）

所以还是说一下这题的思路。

很多题解写的五边形数，可是我太弱了不会……
我们可以把问题分为两部分（看代码）。
第一部分，$1$ 到 $\sqrt{n}$，由于可以确定跑步距离的范围，因此可以把跑步距离看成“物品”用背包来做。

而另外一部分，由于决策范围很大，因此背包 TLE 100%，可以仿照分苹果的方法。

最后就 AC 了。

别忘了取模，否则会超long long