HDU－4651－Partition

ACM模版

题目链接

HDU 4651 Partition

题解

将n拆分成多个正整数之和，问有多少种拆法？
如5 = 1+1+1+1+1 = 1+1+1+2 = 1+1+3 = 1+4 = 5 = 1+2+2 = 2+3.共7种

公式：

f[n]=∑(-1)^(k-1)(f[n-k(3*k-1)/2]+f[n-k*(3*k+1)/2])
其中n-k*(3*k-1)/2>=0,n-k*(3*k+1)/2>=0；
注意两个条件要分开判断，有大于0的就加上相应的f，不是两个同时成立或者不成立

代码

#include <iostream>

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

int main(int argc, const char * argv[])
{
    int T;
    int n;
    init();
    cin >> T;
    while (T--)
    {
        cin >> n;
        cout << dp[n] << '\n';
    }

    return 0;
}