hdu - 4651 - Partition

——>>好經典的問題，但數好大，比賽卡住了。。。

原來，這個問題有個公式計算：

q[i]為第i個廣義五邊形數。
 

#include <cstdio>

using namespace std;
const int maxn = 100000;
const int mod = 1000000007;
int p[maxn+10];

void init(){
    int i, j, k, l;
    long long sum;
    p[0] = 1;
    for(i = 1; i <= maxn; i++){
        sum = 0;
        for(j = 1, k = 1, l = 1; j > 0; k++, l = -l){
            j = i - (3*k*k - k) / 2;
            if(j >= 0) sum += l * p[j];
            j = i - (3*k*k + k) / 2;
            if(j >= 0) sum += l * p[j];
            sum = (sum % mod + mod) % mod;
        }
        p[i] = sum;
    }
}

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