拆分数的四种求法
zhiyangfan
·
2023-01-11 19:50:52
·
个人记录
拆分数的四种求法
为什么是四种吧，没有深意，就是想蹭一下孔乙己的热度。
今天写了一个比赛的 题解。其中的 F 涉及到求分拆数，在群友会 \mathcal{O}(n\sqrt{n}) 薄纱我之后，我决定学习一下。
http://oeis.org/A000041 这是分拆数的 OEIS。它的 OGF 是：
\prod_{n\ge 1}(1-z^n)^{-1}
然后我们来看怎么求这个东西。从 GF 角度出发可以推得
\exp\sum_{n\ge 1}\sum_{m\ge 1}\dfrac{z^{nm}}{m}
如果模数合适这就能求了。
但模数不合适我们就要从其他角度考虑了。首先考虑背包，暴力 \mathcal{O}(n^3) 想怎么做就怎么做。接下来我们想想更优的。
注意到暴力背包的一个瓶颈是我们必须保证所有数字之间无序，而这个限制是很容易规避掉的，换一个循环顺序即可。先枚举数再枚举需要加入的和，容易发现这样一定加入的数不降。
#include
const int N = 1e5 + 10, mod = 1e9 + 7; int f[N];
int main()
{
int n; scanf("%d", &n); f[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j) (f[j] += f[j - i]) %= mod;
for (int i = 1; i <= n; ++i) printf("%d\n", f[i]);
return 0;
}
时间复杂度 \mathcal{O}(n^2)。还能不能更好呢！可以！注意到相加和为某个数这样的限制，很多都和根号有关，这里我们考虑根号分治。
对于大于 \sqrt{n} 的数，最多出现 \mathcal{O}(\sqrt{n}) 次且值域连续，我们考虑一种把 n 种操作转化为 2 种的思路。简单起见，我们把所有的数减去 \sqrt{n}，这样值域就是从 1 开始的连续整数了。考虑设 f_{i,j} 表示选 i 个数和为 j 的方案数。则想到达 f_{i,j} 这个状态，要么在 f_{i-1,j-1} 后面加一个 1，要么给 f_{i,j-i} 中的所有数加上 1。容易发现这样可以构造出所有的合法无序序列。
求完 f 后，我们即可求出 g_{i} 表示只考虑大于 \sqrt{n} 的数，构造出 i 的方案数，然后以这个为基础用所有不大于 \sqrt{n} 的数跑上面的背包即可。时间复杂度 \mathcal{O}(n\sqrt{n})。
#include
#include
const int N = 1e5 + 10, mod = 1e9 + 7; int f[N], g[500][N];
int main()
{
int n; scanf("%d", &n);
int B = sqrt(n); g[0][0] = f[0] = 1;
for (int i = 1; i < 500; ++i)
for (int j = 0; j <= n; ++j)
{
(g[i][j] += g[i - 1][j - 1]) %= mod;
if (j >= i) (g[i][j] += g[i][j - i]) %= mod;
int t = i * B + j; if (t <= n) (f[t] += g[i][j]) %= mod;
}
for (int i = 1; i <= B; ++i)
for (int j = 1; j <= n; ++j) (f[j] += f[j - i]) %= mod;
for (int i = 1; i <= n; ++i) printf("%d\n", f[i]);
return 0;
}
还有其他思路吗！有！
想必大家在高中数列都听说过五边形数，它长这样：
a_n=\frac{n(3n-1)}{2}
然后我们来引入一个广义五边形数列，它对应的是：
\{a_0,a_1,a_{-1},a_{2},a_{-2},\cdots,a_n,a_{-n}\}
容易证明这样是递增的。
然后有一个我不会证的等式是：
\prod_{n\ge 1}(1-z^n)=\sum_{n}(-1)^nz^{\frac{n(3n-1)}{3}}
这就是广义五边形数啊。而又因为它是 \mathcal{O}(n^2) 级别的，所以等式右边在模 z^n 意义下只有 \mathcal{O}(\sqrt{n}) 个非 0 项。而等式左边求逆就是分拆数的 OGF，所以我们求出等式右边后暴力求逆即可得到分拆数。暴力求逆的复杂度是 \mathcal{O}(n\sqrt{n})，把卷积拆开做就行了。（为什么不 \rm NTT 求逆？也行吧，但这样不就又对模数有要求了吗）
#include
#include
#include
const int N = 1e5 + 10, mod = 1e9 + 7; typedef long long ll; int F[N], G[N];
int main()
{
int n; scanf("%d", &n); G[0] = F[0] = 1;
auto f = [&](int i)
{
int u = i * (3 * i - 1) / 2;
if (u > n) return false;
if (i & 1) (G[u] += mod - 1) %= mod;
else (G[u] += 1) %= mod;
return true;
};
for (int i = 1; ; ++i)
{
if (!f(i)) break;
if (!f(-i)) break;
}
std::vector
for (int i = 1; i <= n; ++i) if (G[i]) g.push_back(i);
int now = 0;
for (int i = 1; i <= n; ++i)
{
while (now < (int)g.size() && g[now] <= i) ++now;
for (int j = 0; j < now; ++j)
(F[i] += (ll)G[g[j]] * F[i - g[j]] % mod) %= mod;
F[i] = mod - F[i];
}
for (int i = 1; i <= n; ++i) printf("%d\n", F[i]);
return 0;
}