我其实把ntt忘干净了，只是用它卷积了而已。

可以理解为补充：http://218.28.19.228:8081/cogs/solution/solpl.php?pl=pmxmNJgjk。

3126. 自然数拆分Lunatic版

首先考虑n是2000的正整数拆分，正常可以用完全背包的办法搞定，这里我们考虑另一种办法。我们维护当前的递减序列的时候，每次操作都可以是把这堆数垫一层或者对着结尾放一个 $1$，就是这样：

这里每个竖着的格子高度代表了我们维护递减序列的值，绿色1就代表整体加一，后面一个小格子2就是往末尾加上了一个1。

所以说我们可以记录 $dp_{i,j}$ 表示选了 $i$ 个数，然后和是 $j$，所以说我们转移式子就是 $dp_{i,j}=dp_{i,j-i}+dp_{i-1,j-1}$，分别对应两种情况。

时间复杂度 $O(n^2)$，于是我们解决了3126. 自然数拆分Lunatic版。注意要减一因为看样例可以发现不能保留只有一个数的情况。

HS的自然数拆分2

就是上面的问题把 $n$ 改成 $100000$，然后不能重复。

根据不能重复，我们发现选连续一堆数加起来，从最小的 $1$ 开始加不能到 $\sqrt n$ 个（根据等差数列求和公式）。

所以HS就告诉我们可以用根号分治了，就是先考虑不超过 $\sqrt n$ 的数让他们和为 $n$ 的方案数，可以做到 $O(n\sqrt n)$，然后剩下大于 $\sqrt n$ 的显然选的个数也是有限制的，用我们上面的办法也可以 $O(n\sqrt n)$。

话说不能重复怎么办呢？我们上面的1操作是不会让原本合法的变成不合法的，只有可能是连续加了两个 $1$ 进去才会，所以说我们每次执行2操作之前先执行1一次就可以了。

细节上我们做问题后半部分的时候，2操作每次就不是加一了，而是我们规定的分治界限 $b$。

合并答案就按照定义来就可以，我的写法是把后半部分 dp 的数组对于 $n-i$ 的和枚举个数加起来，然后用这玩意乘上前一个和为 $i$ 的。

于是解决了HS的自然数拆分2，写的时候注意一下模数太大longlong会爆炸。

HS的自然数拆分

首先考虑只有一个数的情况。

相比于上一个问题，其实就是可以重复了。前半部分不说了，后半部分其实就是我们1和2操作分开做就可以了。

下面是HS晚上没讲的东西（相当于我刚刚一直在复述）

现在问题在怎么处理出每个的答案，发现对于$k$这个数的答案就是$\sum_{i=0}^k dp1_{i} \times sumdp2_{k-i}$，这里 $dp1$ 是我们前一半处理的，$sumdp2$ 是对于一个固定和的所有选数个数情况的和，这就是一个卷积的形式，直接跑ntt即可，$998244353$的原根是$3$。

怎么还要写简单的多重背包，我不是明天期末考吗。