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;
}

补充：软件开发 , C++ ,

上一个：C++子类析构问题
下一个：hdu1166 树状数组