自动搬运

查看原文

来自洛谷，原作者为

	OMG_wc 幻想家协会会长

搬运于2025-08-24 22:18:22，当前版本为作者最后更新于2020-03-08 09:52:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题就是正整数拆分问题，很容易想到一种 $O(n^2)$ 的 DP：

记 $f_{i,j}$ 表示用了前 $i$ 个数和为 $j$ 的方案数，那么 $f_{i,j}=f_{i-1,j}+f_{i,j-i}$，初始时 $f_{0,0}=1$ 。

这其实就是完全背包，但只能拿 $70$ 分（也可能乱搞到 $80$ 分）。

那么怎么办呢？我们采用分块的思路，令 $m=\sqrt n$，对于 $i<m$ 的数采用以上完全背包来求，这部分时间复杂度为 $O(n\sqrt n)$ 。

而对于大于等于 $m$ 的数，采用另外一种 DP：

记 $g_{i,j}$ 表示用了 $i$ 个大于等于 $m$ 的数和为 $j$ 的方案数，那么 $g_{i,j}=g_{i-1,j-m}+g_{i,j-i}$，初始时 $g_{0,0}=1$ 。

• 转移方程的第一项 $g_{i-1,j-m}$ 表示在拆分序列中增加一个数 $m$ 。
• 转移方程的第二项 $g_{i,j-i}$ 表示把当前拆分序列的每个数都加上 $1$。

$i$ 最大为 $\sqrt m$，因而这一步时间复杂度为 $O(n\sqrt n)$ 。

如果觉得不好理解，可以随便举个例子：

假设当前 $m=1$，你要拆的数是 $11$，其中一种方案是 $11=5+2+2 +2$。初始拆分序列为空，现在有两种操作：操作 $1$ 是在拆分序列中增加一个数 $1$，操作 $2$ 是把当前序列中每个数都增加 $1$ 。那么该方案对应的操作序列为：$12221112$。

容易发现，一种拆分方案和一种操作序列是一一对应的，因此这样 DP 不会重复也不会遗漏。

最后一步，就是把分块的两部分结合一下。枚举第一个部分的总和为 $j$，那第二个部分的总和就为 $n-j$，把两者的方案数乘起来记入答案中，即为 $\sum\limits_{j=0}^n (f_{m-1,j}\times \sum\limits_{i=0}^{m} g_{i,n-j})$。

那么本题总时间复杂度为 $O(n\sqrt n)$ ，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int f[N];
int g[400][N];
int main() {
    int n, p;
    cin >> n >> p;
    int m = sqrt(n) + 1;
    f[0] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = i; j <= n; j++) {
            f[j] += f[j - i];
            f[j] %= p;
        }
    }
    g[0][0] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = i; j <= n; j++) {
            g[i][j] = g[i][j - i];
            if (j >= m) g[i][j] += g[i - 1][j - m];
            g[i][j] %= p;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        LL sum = 0;
        for (int j = 0; j < m; j++) sum += g[j][n - i];
        sum %= p;
        ans = (ans + f[i] * sum) % p;
    }
    cout << ans << endl;
    return 0;
}