题解 P6189 【[NOI Online 入门组]跑步（民间数据）】
OMG_wc
·
·
题解
本题就是正整数拆分问题，很容易想到一种 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。
如果觉得不好理解，可以随便举个例子：
假设当前 $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)$ ，代码如下：
```cpp
#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;
}
```