拆分数的四种求法

· · 个人记录

拆分数的四种求法

为什么是四种吧，没有深意，就是想蹭一下孔乙己的热度。

今天写了一个比赛的 题解。其中的 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 <cstdio>
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 <cmath>
#include <cstdio>
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 <cstdio>
#include <vector>
#include <algorithm>
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<int> g;
    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;
}