<span>HDU4651 Partition（整数拆分模版）</span>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using namespace std;
const int mod=1e9+7;
int dp[100010];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1;i<=100000;i++)
    {
        for(int j=1,r=1;i-(3*j*j-j)/2>=0;j++,r*=-1)
        {
            dp[i]+=dp[i-(3*j*j-j)/2]*r;
            dp[i]%=mod;
            dp[i]=(dp[i]+mod)%mod;
            if(i-(3*j*j+j)/2>=0)
            {
                dp[i]+=dp[i-(3*j*j+j)/2]*r;
                dp[i]%=mod;
                dp[i]=(dp[i]+mod)%mod;
            }
        }
    }
}
int main()
{
    int t,n;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",dp[n]);
    }
    return 0;
}