「解题报告」[ABC221H] Count Multiset

K8He · 2023-07-28 14:44:30 · 题解

校内学长搬的模拟赛题，赛时爆标了，来写一发。

首先为了方便，先不考虑相同元素出现次数的限制。

我们设 f_{i, j} 表示当前填了 i 个数，总和为 j 的方案数。

考虑一种奇妙的转移方式：

• 向当前序列里加上一个 0，即从 f_{i - 1, j} 转移过来。
• 将当前序列全部加 1，即从 f_{i, j - i} 转移过来。

第一种操作的例子是序列 2 2 3 加上一个 0 得到 0 2 2 3，由 f_{3, 7} 转移到 f_{4, 7}；第二种操作的例子是 0 0 1 2 整体加 1 变为 1 1 2 3，由 f_{4, 3} 转移到 f_{4, 7}。

接下来开始考虑相同元素出现次数的限制。

既然有限制就不能随意加零，那么第一种操作贡献就应该是 \sum_{k = 1}^{m}f_{i - k, j}，但是我们不知道之前的 f_{i - k, j} 有几个零，这样就不能直接转移。

考虑设一个辅助的 g_{i, j} 表示当前填了 i 个数，总和为 j 且 序列里不含有 0 的方案数。