设dp[n]为整数n的分割函数，由五边形定理得到：
dp[n] = dp[n-1] + dp[n-2] - dp[n-5] - dp[n-7]……
我们将其分为两部分计算
第一部分为 :( dp[n-1] - dp[n-5] …… ) 奇数项为加，偶数项为减，第j项括号内的值为 ： n-(j*(3*j-1)/2)
第二部分为：(dp[n-2] - dp[n-7]……) 奇数项为加，偶数项为减，第j项括号内的值为 ： n-(j*(3*j+1)/2)
如此递推便可求出n的分割函数 dp[n]
#include <iostream>
#include <cmath>
#include <string.h>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define MAXSIZE 1000005
#define INF 1e11 const LL mod=1e9+; LL dp[MAXSIZE]; LL Solve(int n)
{
dp[] = ;
for(int i=;i<=n;i++)
{
for(int j=;j*(*j-)/<=i;j++)
{
if(j&)
dp[i] = (dp[i] + dp[i-(j*(*j-)/)] + mod)%mod;
else
dp[i] = (dp[i] - dp[i-(j*(*j-)/)] + mod)%mod;
} for(int j=;j*(*j+)/<=i;j++)
{
if(j&)
dp[i] = (dp[i] + dp[i-(j*(*j+)/)] + mod)%mod;
else
dp[i] = (dp[i] - dp[i-(j*(*j+)/)] + mod)%mod;
}
}
return dp[n];
} int main()
{
int n;
scanf("%d",&n);
LL ans = Solve(n);
printf("%lld\n",ans);
return ;
}