我其实把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$。

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

HS：这题考察基本功（诶自然数拆分怎么做我看看）。

一个基础的观察：对于物品 $i$，当 $i\ge\sqrt{n}$ 时物品不可能取完，所以这部分是一个完全背包。

问题分成了两部分，设 $B=\lceil\sqrt{n}\rceil$，令 $F_i$ 表示只用 $1\sim B$ 这些物品体积为 $i$ 的方案数，$G_i$ 表示只用 $B+1\sim n$ 这些物品体积为 $i$ 的方案数，最后对 $F,G$ 卷一下即可。

对于 $F_i$：就是一个裸的完全背包，单调队列可以 $O(n\sqrt{n})$，但因为计数背包是可以退的，所以直接记录前缀和就可以 $O(n\sqrt{n})$。

对于 $G_i$：选择的物品不超过 $\sqrt{n}$ 个，考虑设 $g_{i,j}$ 表示这部分选择 $i$ 个物品体积和为 $j$ 的方案数，为了避免记重强制选择的物品体积单调递减。

问题变成了对一个单调递减，和为 $j$，最小数超过 $\sqrt{n}$ 的序列计数。如何刻画单调递减，经典做法是维护一个空数列，每次全局加一，或者在末尾加入一个最小元素，因此可以得出转移式 $g_{i,j}=g_{i,j-i}+g_{i-1,j-B-1}$。状态数是 $O(n\sqrt{n})$，转移是 $O(1)$ 的。

综上，在 $O(n\sqrt{n})$ 的时间复杂度内解决了本题。

比较经典的计数题。

考虑 $\sum a_i^2$ 的组合意义，等价于枚举两个取球方案，且两个方案最终取得的序列相同的方案数。

设 $f_{i,j,k}$ 表示取了 $i$ 个球，枚举的两个方案中，第一个方案在上侧取了 $j$ 个球，在下册取了 $k$ 个球。且目前两种取球的方案得到的序列一样的方案数。

枚举第 $i+1$ 个球取上面还是下面，转移即可，滚动数组优化空间，即可做到 $O(n^3+n^2m))$ 的时间复杂度和 $O(n^2)$ 的空间复杂度。