题目：http://acm.hdu.edu.cn/showproblem.php?pid=4658
题目大意：给你两个个数n，k，要求你算出把n拆分，且每个数的个数都不超过k的种数。
思路：五边形定理。。 具体可以看看我转的那篇文章，写得挺详细的。。再贴一个在别人博客看到的一个关键的东西：
part is repeated k or more times)
对于(1-x^k)*(1-x^2k)*...*(1-x^nk)，可令x^k=y;再利用五边形定理将其打开；
两个式子相除那里是直接用等比数列数和就可以得出来，这里想了半天，问学长才知道的。。= =
先贴个代码，代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 lld;
const int MOD = 1e9 + 7 ;
const int MAXN = 100001;
lld get_q(lld x)
{
lld ans = (lld)3*x*x-x;
return ans/2;
}
lld Q[MAXN],P[MAXN];
void init()
{
Q[0] = 0;
for(int i = 1;i<MAXN;i++)
{
if(i&1) Q[i] = get_q(i/2+1);
else Q[i] = get_q(i/2*(-1));
}
P[0] = P[1] =1;
for(int i = 2;i<MAXN;i++)
{
for(int j = 1;;j++)
{
if(Q[j]>i) break;
int t = j;
if(t&1) t = t/2 + 1;
else t = t/2;
if(t&1) P[i] = P[i] + P[i - Q[j]];
else P[i] = P[i] - P[i - Q[j]];
if(P[i]>MOD) P[i] = P[i]%MOD;
if(P[i]<0) P[i] = P[i]+MOD;
//P[i] = (P[i]%MOD+MOD)%MOD; 这样写超时。。
}
}
}
lld solve(int n,int k)
{
lld ans = 0;
for(int i = 0;;i++)
{
if(Q[i]*k>n) break;
int t = i;
if(t&1) t = t/2 + 1;
else t = t/2;
if(t&1) ans = ans - P[n - Q[i]*k];
else ans = ans + P[n - Q[i]*k];
if(ans>MOD) ans = ans%MOD;
if(ans<0) ans = ans+MOD;
//ans = (ans%MOD+MOD)%MOD; 这样写超时。。
}
return ans;
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
printf("%I64d\n",solve(n,k));
}
return 0;
}