51Nod-1259-整数划分 V2

ACM模版

描述

题解

这道题有一个相关问题用的是dp，于是想着这道题也可以用dp，结果尝试了半天未果，最后看了讨论区的内容，发现原来需要用到一个公式——欧拉的五边形定理。实际上，虽然这道题是用公式解得，但是同样是dp。

P(n)表示n的划分种数。

P(n) = ∑{P(n - k(3k - 1) / 2 + P(n - k(3k + 1) / 2 | k ≥ 1}
n < 0时，P(n) = 0, n = 0时, P(n) = 1即可。

代码

#include <cstdio>

#define f(x) (((x) * (3 * (x) - 1)) >> 1)
#define g(x) (((x) * (3 * (x) + 1)) >> 1)

using namespace std;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int n, ans[MAXN];

int main()
{
scanf("%d", &n);

    ans[0] = 1;
for (int i = 1; i <= n; ++i)
    {
for (int j = 1; f(j) <= i; ++j)
        {
if (j & 1)
            {
                ans[i] = (ans[i] + ans[i - f(j)]) % MOD;
            }
else
            {
                ans[i] = (ans[i] - ans[i - f(j)] + MOD) % MOD;
            }
        }
for (int j = 1; g(j) <= i; ++j)
        {
if (j & 1)
            {
                ans[i] = (ans[i] + ans[i - g(j)]) % MOD;
            }
else
            {
                ans[i] = (ans[i] - ans[i - g(j)] + MOD) % MOD;
            }
        }
    }

printf("%d\n", ans[n]);

return 0;
}

参考

《整数划分》