划分数

模型A

$n$ 个相同的小球，放进 $m$ 个箱子，每个箱子至少一个球，箱子彼此相异，即 (1+2+1 和 1+1+2) 算作不同的划分方式，问有几种划分方式。

直接插板法即可。

$\mathtt{ans} = \binom{n-1}{m-1}$

变形：可以有空箱。

在第一个球左边和最后一个球右边分别再加一个空位。

$\mathtt{ans} = \binom{n+1}{m-1}$

随便用啥方法写个组合数就好了。

$n$ 个相同的小球放进 $m$ 个相同的箱子，可以有空箱，问有几种不同的划分方式。

即 $1+2+1$ 和 $1+1+2$ 是一种划分方式。

考虑递推。

令 $f_{i,j}$ 表示 $i$ 个球，放进 $j$ 个箱子的答案。

显然，若此时划分方式中有空箱，将一个空箱去掉即可，其贡献为 $f_{i, j-1}$ 。

否则将每个箱子中都去掉一个球，其贡献为 $f_{i-j, j}$

综上，有递推式 $f_{i,j}=f_{i,j-1}+f_{i-j,j}$

特别地， $f_{i,1}=1，f_{0,i}=1$ 。

一般地，我们考虑每个箱子至少有 $k$ 个的情况，此时将 $n$ 减去 $mk$ 即可，可看作提前在每个盒子里放了 $k$ 个球。

更加一般地，考虑有上下界的划分情况，即每个盒子中的球的个数在 $[l,r]$ 范围内。

容斥计数： $\mathtt{ans} = f_{n-ml,m} - f_{n-mr-m,m}$

可利用二元生成函数及多项式技巧进行优化，在此不予展示。

在 $\mathtt{B}$ 的基础上对盒子中球的个数的奇偶性有限制。

$f_{i,j}$ 盒子中全为奇数， $g_{i,j}$ 盒子中全为偶数。

$g_{i,j} = f_{i-j, j}$ （在每个盒子里再放一个）

$f_{i,j} = f_{i-1,j-1}+g_{i-j,j}$ （在每个盒子里再放一个或者增加一个放了一个的盒子）

将 $n$ 划分成若干个数之和，求出这些数的乘积的最大值及划分方式。