【题解】整数划分 $O(n \sqrt n)$的 Naive 做法

litble 刚刚发了一篇介绍五边形数定理做整数划分，能做到 $O(n \sqrt n)$预处理，$O(1)$询问的文章，可以戳这里：https://www.mina.moe/archives/10981

本篇文章就介绍一个 Naive 的 Dp 做法吧，$O(n \sqrt n)$询问

整数划分其实可以看作完全背包问题，只是复杂度 $O(n ^ 2)$有点大了

考虑把物品分类，重量 $ < \sqrt n$的分一类，重量 $\geq \sqrt n$的分一类

重量 $ < \sqrt n$的直接完全背包做就行了

重量 $\geq \sqrt n$的选中物品总数不会超过 $\sqrt n$，因此设状态 $f[i][j]$为选择 $i$个物品，总重量为 $j$的方案数

有如下状态转移方程：

$$f[i][j] = f[i – 1][j – \sqrt n] + f[i][j – i]$$

第一项表示新增一个重量为 $\sqrt n$的物品（即能选中的最小重量）

第二项表示让接下来要选择的 $i$个物品都提高自己的姿势水平，使得这 $i$个物品比前面选的物品都要重（不知道高到哪里去了），这样就能保证最终选择的物品重量序列不降啦（方案不重）！

两个 Dp 都是 $O(n \sqrt n)$的

代码：

#include <bits/stdc++.h>

#define NS (200005)
#define MOD (999999599)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, k, f[NS], g[2][NS], h[NS];

int main(int argc, char const* argv[])
{
    IN(n), k = sqrt(n), f[0] = 1;
    for (int i = 1; i < k; i += 1)
        for (int j = i; j <= n; j += 1)
            f[j] = (f[j] + f[j - i]) % MOD;
    g[0][0] = h[0] = 1; bool cur = 0;
    for (int i = 1; i <= n / k; i += 1)
    {
        cur ^= 1, memset(g[cur], 0, sizeof(int) * (n + 1));
        for (int j = 0; j <= n; j += 1)
        {
            if (j >= k) g[cur][j] = (g[cur][j] + g[cur ^ 1][j - k]) % MOD;
            if (j >= i) g[cur][j] = (g[cur][j] + g[cur][j - i]) % MOD;
        }
        for (int j = 0; j <= n; j += 1) h[j] = (h[j] + g[cur][j]) % MOD;
    }
    int tot = 0;
    for (int i = 0; i <= n; i += 1)
        tot = (tot + (1ll * f[i] * h[n - i] % MOD)) % MOD;
    printf("%d\n", tot);
    return 0;
}