分拆数的四种求法
木xx木大
·
·
算法·理论
分拆数有四种求法，你知道吗？
定义： 记 P_n 为将 n 拆分成若干无序正整数的和的方案数。
模板题：loj 6268。n\le 10^5，答案对 998244353 取模。
例题：P6189 [NOI Online #1 入门组] 跑步（其实也是模板啦）
方法一
这个问题非常像完全背包。但 O(n^2) 过不去。考虑根号分治：
-
对于小于 \sqrt n 的数，暴力完全背包。
-
对于大于 \sqrt n 的数，设 g_{i,j} 表示用了 i 个 >m 的数，和为 j 的方案数，dp 一下，转移为 g_{i,j}=g_{i-1,j-m}+g_{i,j-i}。前者表示加入一个 m ，后者表示将现在的序列整体+1。
容易发现第一维大小只有 \sqrt n 级别。
-
把两部分卷起来即可。
方法二
类似付公主的背包的做法。分拆数的 OGF 为
P(x)=\prod_{k=1}\sum_{i=0}x^{ik}=\prod_{k=1}\frac{1}{1-x^k}=\exp\sum_{k=1}\ln\frac{1}{1-x^k}=\exp\sum_{k=1}\sum_{i=1}\frac{x^{ik}}{i}
后面的求和可以 O(n\log n) 计算。具体见P4389 付公主的背包 题解
方法三
前置知识：五边形数
五边形数是能排成五边形的多边形数。
如图，前几项为 1,5,12,22\dots，其通项公式为 \frac{3n^2-n}{2}
广义五边形数： n 可以取负数，其通项公式为\frac{3n^2\mp n}{2}
五边形数定理
定义欧拉函数 \phi(x)
\begin{aligned}
\phi(x)&=\prod_{i=1}(1-x^i)\\&=1-x-x^2+x^5+x^7-x^{12}-x^{15}+\dots\\
&=1+\sum\limits_{i=1}(-1)^ix^{i(3i\pm 1)/2}
\end{aligned}
这条等式被称为五边形数定理。证明比较复杂，故不展开叙述。有兴趣的可以看 visit_world的博客
将 \phi 与 P 乘起来
\begin{aligned} \phi(x)\sum_{k=0}^{\infty}p(k)x^k =& (1-x-x^2+x^5+x^7-\ldots)\\&(1+p(1)x+p(2)x^2+p(3)x^3+\ldots)\\ =& 1 \end{aligned}
将整个式子展开，得到：
p(k)-p(k-1)-p(k-2)+p(k-5)+p(k-7)-\ldots=0
### 方法四
#### 前置知识：Ferrers diagram
一个分拆的 Ferrers 图，是把分拆出的每一项，用点（或方格）组成的行来表示。一般分拆写为递减正整数和，所以 Ferrers 图也用长度递减的行来表示。
Ferrers 图与分拆之间是一一对应的。如 14=6+3+3+2 的一个分拆的 Ferrers 图如下：
通过读它的列，得到的 Ferrers 图与原图互为共轭。
##### 引申
* 对于所有行数不超过 $m$ 的 Ferrers 图，都唯一对应一个列数不超过 $m$ 的共轭图。因此整数 $n$拆分成 $m$ 个数的和的拆分数，和数 $n$ 拆分成最大数为 $m$ 的拆分数相等。
* 整数 $n$ 拆分成最多不超过 $m$ 个数的和的拆分数，和 $n$ 拆分成最大不超过 $m$ 的拆分数相等。
* 整数 $n$ 拆分成互不相同的若干奇数的和的拆分数，和 $n$ 拆分成自共轭的Ferrers图像的拆分数相等。例如：17=9+5+3
考虑从 Ferrers diagram 的原点引出一条 $y=x$ 的直线，它离开这个图的位置就框处了一个 $h \times h$ 的正方形，这个正方形被称为一个整数拆分的 Durfee square。
如果我们确认了正方形的边长是 $h$，它两侧放置的就都是 $\le h$ 的整数划分。因此我们得到了这样的表达式：
$$
\prod_{k\ge1} \frac1{1-x^k} = \sum_{h\ge0} x^{h^2} \left(\prod_{k=1}^h \frac1{1-x^k}\right)^2
$$
在计算前 $n$ 项时，由于 $h^2\le n$，枚举 $h$ 的上界为 $\sqrt n$，复杂度为 $O(n\sqrt n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
int n,mo;
const int N=1e5+5;
int ans[N],tmp[N];
void work()
{
scanf("%d%d",&n,&mo);
int b=sqrt(n);
ans[0]=tmp[0]=1;
for(int i=1;i<=b;i++)
{
for(int k=0;k<2;k++)
for(int j=i;j<=n-i*i;j++)
tmp[j]=(tmp[j]+tmp[j-i])%mo;
for(int j=i*i;j<=n;j++)
ans[j]=(ans[j]+tmp[j-i*i])%mo;
}
printf("%d\n",ans[n]);
}
}
int main()
{
FGF::work();
return 0;
}
```
### 不会证的结论
* 对于 $n$ 的分拆，各个分拆方案中出现至少 $k$ 次的数的个数和，等于所有方案中 $k$ 出现的总次数。详细见[整数分拆中的一个出人意料的结论](http://www.matrix67.com/blog/archives/6348)
* 对任意正整数，其奇分拆数目（每个部分均为奇数）等于其互异分拆（每个部分互不相同）数目。证明见《组合数学》
### References
* [多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan)
* [EI：分拆数的第三种计算方法](https://blog.csdn.net/EI_Captain/article/details/104729572)
* 图片主要来自百度百科