HDU:4651 Partition

經典的整數劃分問題。

使用O（n^2）的辦法必逾時。

用這個公式可以遞推出來。

注意n-k*(3*k-1)/2>=0,n-k*(3*k+1)/2>=0。

注意某些地方可能溢出int，是以用longlong比較安全。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#define ll long long
#define INF 2139062143
#define MOD 1000000007
#define MAXN 100005
using namespace std;
int p[MAXN];
void Init()
{
    p[0]=1;
    for(int i=1; i<=100000; ++i)
    {
        for(int k=1; ; ++k)
        {
            int a=i-(ll)k*(3*k-1)/2,b=i-(ll)k*(3*k+1)/2;
            if(a<0&&b<0) break;
            ll temp=0;
            if(a>=0) temp=(temp+p[a]+MOD)%MOD;
            if(b>=0) temp=(temp+p[b]+MOD)%MOD;
            if((k+1)&1) temp=(-temp+MOD)%MOD;
            p[i]=(p[i]+temp+MOD)%MOD;
        }
    }
}
int main()
{
    Init();
    int T;
    scanf("%d",&T);

    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",p[n]);
    }
    return 0;
}