去 大佬的博客 学习了一下相关知识.
整数划分问题
将一个正整数 $n$ 拆分成若干正整数之和,求方案数.
令 $f(i,j)$ 表示将 $j$ 拆成 $i$ 个数的方案数,转移有 $f(i,j)=f(i,j-i)+f(i-1,j-1)$ ,边界为 $f(0,0)=1$ .
意义是所有数都 $+1$ 或者新加入一个 $1$ ,时间复杂度 $O(n^2)$ .
几个拓展
要求拆成的正整数两两不同.这样,新加入一个 $1$ 之前的操作必须是每个数都 $+1$ .
$f(i,j)=f(i,j-i)+f(i-1,j-i)$ .显然不超过 $\sqrt n$ 个数,时间复杂度 $O(n\sqrt n)$ .
要求拆成的数全部为奇数.方案数等同于拆成两两不同的方案数.可以构造出一一对应的映射( $Ferrers$ 图转置).
要求拆成若干个大小 $\le k$ 的正整数.方案数等同于拆成 $\le k$ 个任意大小的正整数.
五边形数定理
五边形数
$f_1=1,f_n=f_{n-1}+3n-2$ .对差分求前缀和,得到 $f_n=\frac{n(3n-1)} 2$ .
$1,5,12,22,35,51,70,92,117,145,176,210,247,287\dots$
广义五边形数
在公式 $f_n=\frac{n(3n-1)} 2$ 中, $n$ 取 $0,1,-1,2,-2\dots$
$0,1,2,5,7,12,15,22,26,35,40,51,57,70,77,92,100,117,126\dots$
欧拉函数
$$
\phi(x)=\prod_{i=1}^{+\infty} (1-x^i)
$$
它仅在 $|x|< 1$ 时收敛,但这里作为形式幂级数,我们不考虑它的敛散性.
五边形数定理
$$
\begin{aligned}
\phi(x)&=1-x-x^2+x^5+x^7-x^{12}-x^{15}\dots \\
&=1+\sum_{i=1}^{+\infty}(-1)^i(x^{i(3i-1)/2}+x^{-i(-3i-1)/2})
\end{aligned}
$$
$x^{i(3i-1)/2}$ , $x^{-i(-3i-1)/2}$ 的次数分别是相邻的两个广义五边形数.
五边形数定理与整数划分
写出整数划分问题的生成函数 $G(x)$ ,显然,
$$
\begin{aligned}
G(x)&=\prod_{i=1}^{+\infty}(1+x^i+x^{2i}+x^{3i}+\dots) \\
&=\prod_{i=1}^{+\infty}\frac 1 {1-x^i}
\end{aligned}
$$
发现 $G\times \phi=1$ .把多项式乘法暴力展开,观察系数,可以得到递推式
$$
G(1)=1,G(n)=G(n-1)+G(n-2)-G(n-5)-G(n-7)+\dots
$$
因为广义五边形数的级别是 $n^2$ 的,所以直接递推的时间复杂度为 $O(n\sqrt n)$ .
也可以直接在模 $x^{n+1}$ 意义下对 $\phi$ 求逆得到 $G$ ,时间复杂度 $O(n\log n)$.
Loj 6268 分拆数
模板题,对 $\phi$ 求逆得到 $G$ .