题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4658
题意:给出n、k。求n的拆分方案数。要求拆分中每个数不超过k。
i64 f[N];
void init()
{
f[0]=f[1]=1; f[2]=2;
int i,j,k,t;
for(i=3;i<N;i++) for(j=1;;j++)
{
FOR0(k,2)
{
if(!k) t=(3*j*j-j)/2;
else t=(3*j*j+j)/2;
if(t>i) break;
if(j&1) f[i]=(f[i]+f[i-t])%mod;
else f[i]=(f[i]-f[i-t])%mod;
}
if(t>i) break;
}
}
int n,m;
i64 cal()
{
i64 ans=f[n];
int i,j=-1,k;
for(i=1;;i++,j=-j)
{
k=(3*i*i-i)/2*m;
if(k>n) break;
ans=(ans+f[n-k]*j)%mod;
k=(3*i*i+i)/2*m;
if(k>n) break;
ans=(ans+f[n-k]*j)%mod;
}
if(ans<0) ans+=mod;
return ans;
}
int main()
{
init();
rush()
{
RD(n,m);
PR(cal());
}
}