51Nod-1259-整数划分 V2

时间:2022-07-04 18:40:58

ACM模版

描述

51Nod-1259-整数划分 V2

题解

这道题有一个相关问题用的是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;
}

参考

《整数划分》