前言
感觉大家应该都很早接触过分拆数这个逆天东西，因为形式比较灵活多变啊。感觉初赛就有几个这样的题。
当然在分拆数以外还有一些划分数相关的小内容。
基础内容
以下问题皆讨论无序的情况：也就是，划分出的数是单调不降的。
- 将 \(n\) 划分成 \(k\) 个数的方案数
设 \(f(n,k)\) 表示答案，如果没有 \(1\)，则答案为 \(f(n-k,k)\)，否则答案为 \(f(n-1,k-1)\)，二者相加就是答案。
- 将 \(n\) 划分成 \(\le k\) 个数的方案数。
设 \(f(n,k)\) 表示答案，若没有空的组，则答案为 \(f(n-k,k)\)，否则答案为 f(n,k-1)$。
- 将 \(n\) 划分成若干个数，其中最大值 \(\le k\)
等价于上面的问题：写成点阵形式，则无非是从行还是从列的角度看这个拆分问题。
- 将 \(n\) 划分成 \(k\) 个互不相同的整数
首先我们都知道 \(k\) 是\(O(\sqrt{n})\) 的。同样考虑写成点阵形式，我们会发现相当于把 \(n\) 用若干个 \(1\sim k\) 内的整数划分且每个数都出现至少一次。
设 \(f(n,k)\) 表示答案，则有 \(f(n,k)=f(n-k,k)+f(n-k,k-1)\)。
- 将 \(n\) 划分成若干个 \(\le m\) 的数
设 \(f(n,m)\) 为答案，若最大值 \(=m\) 则答案为 \(f(n-m,m)\) 否则答案为 \(f(n,m-1)\)。
- 将 \(n\) 划分成若干个互不相等，且 \(\le m\) 的数
修改第一种情况变为 \(f(n-m,m-1)\) 即可。
其实不管怎么搞，设个二维 dp 先，然后随即应变一下就好了。
比如说：把 \(n\) 划分成 \(m\) 个模 \(p\) 余 \(k\) 的数，那么我们也可以在 \(O(nmp)\) 的时间内解决。
还有一个，和确定，让乘积尽可能大的划分，我还记得学而思给了一句口诀啊：多 \(3\) 少 \(2\) 不要 \(1\)，就是你首先只能出现 \(2,3\)，在这个基础上让 \(3\) 尽可能多就行。
如果我们要让划分出来的数互不相同且乘积最大的话，也是可以做的：
设 \(S(x)=\sum_{i=2}^{x}i\)，找到第一个 \(\ge n\) 的 \(S(x)\)。
若相等，则拆分方式就是 \(S_x\)。
若 \(S(x)=n+1\)，去掉 \(2\)，让 \(x\) 变成 \(x+1\)。
否则直接去掉 \(S(x)-n\)。
我不会证明这个啊。
一些题目
多重集计数
设 \(f(n,m,k)\) 是满足以下条件的多重集数量：
-
元素和为 \(n\)
-
每个元素出现次数 \(\le m\)
-
元素个数为 \(k\)。
给定 \(n,p\)，输出 \(n^2\) 个 \(f(n,x,y)，1\le x,y\le n\) 的值，分别模 \(p\) 的结果。
\(n\le 4000\)。
首先要求 \(n^2\) 个信息的话我们就很难在 \(O(1)\) 的均摊时间内维护，所以我们觉得正解肯定在 \(n^2\) 外带个 \(\log n\) 或者 \(\sqrt{n}\) 的状物。
首先这个题如果 \(m\) 固定那么就是套用 ABC221H 的做法，在 \(n^2\) 的时间内求出 \(n\) 个值：很简单，我们考虑多重集的差分即可（发现很多带递增的问题，用差分考虑会非常合适）。
这个显然没有出路。但我们可以得到 \(O(n^3)\) 的做法。
仔细一想 \(m=1\) 的时候似乎只有 \(\sqrt{n}\) 个点值啊，所以我们猜测不为 \(0\) 的答案数不是很多？
分析以后会发现 \(m\) 固定的时候 \(k\) 的上界是 \(\sqrt{nm}\)，这给我们枚举有意义的 \((m,k)\) 然后直接计算 \(f(m,k)\) 带来了可能。
我们考虑去掉一个 \(m\) 的限制，则可以用上面的基本模型解决。
考虑对 \(m\) 这个条件进行容斥：就是我们枚举一个 \(S\) 集合，这里面的数出现的次数 \(\gt m\)，显然我们要枚举 \(S\) 集合的大小以及元素和，这看起来是信息量很多的，但首先所有 \(g(sum,cnt)\) 可以 \(O(n\sqrt n)\) 预处理，上面已经提到过。
考虑精细算一下复杂度，显然 \(m\) 固定以后要算 \(\sqrt{nm}\) 次，每次的话 \(sum\) 的上界是 \(O(\frac{n}{m})\)，而 \(cnt\) 的上界是 \(O(\frac{\sqrt{nm}}{m})\)，三个量乘起来是 \(O(\frac{n^2}{m})\)，对所有 \(m\) 求和是 \(O(n^2 \ln n)\)。
牛的题。
五边形数定理
咕。
标签：le,分拆,sqrt,划分,答案,我们,小记 From： https://www.cnblogs.com/Cry-For-theMoon/p/16908195.html