这题，明显考察搜索能力。。。在中文版的*中找到了公式。
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define MOD 1000000007
#define LL __int64
LL dp[];
int que[],flag[];
int main()
{
int i,n,t,j,num;
LL x;
num = ;
for(i = ;;i ++)
{
t = (*i*i - i)/;
if(t > ) break;
flag[num] = i;
que[num++] = t;
t = (*i*i + i)/;
flag[num] = i;
que[num++] = t;
}
dp[] = ;dp[] = ;
dp[] = ;
for(i = ;i <= ;i ++)
{
for(j = ;j <= ;j ++)
{
if(que[j] > i)
break;
else
x = dp[i-que[j]];
if(flag[j]% == )
{
dp[i] = (dp[i] + x)%MOD;
}
else
{
dp[i] = (dp[i] - x)%MOD;
if(dp[i] < )
dp[i] += MOD;
}
}
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%I64d\n",dp[n]);
}
return ;
}