AT_abc221_h [ABC221H] Count Multiset 笔记

一种对正整数拆分进行 DP 的转移方法：

考虑两种操作，放 $0$ 和全部 $+1$，容易发现每一种拆分都可以通过这两种操作还原。

因此设 $f_{i,j}$ 表示拆分成 $i$ 个数，和为 $j$ 的拆分方案数，边界条件有 $f_{i,0}\leftarrow [i\le m]$。

接着转移：

• 放 $0$：$f_{i,j}\leftarrow f_{i-1,j}$
• $+1$：$f_{i,j}\leftarrow f_{i,j-i}$

问题是不能连续执行超过 $m$ 次放 $0$ 操作。考虑一次执行所有连续的放 $0$ 操作，用辅助数组 $g_{i,j}$ 表示 $f_{i,j}$ 最后一次执行的操作是 $+1$，这样子放 $0$ 时，$f_{i,j}\leftarrow \sum _{k=i-m}^{i-1}{g}_{k,j}$，前缀和优化，状态数 $O(n^2)$，转移 $O(1)$，时空复杂度 $O(n^2)$。