题解

思路

最终每个集合至多含每种值一次。把值的出现次数与最终集合大小看成二分图两侧的度数，利用 Gale–Ryser 条件判定一个整数分拆是否合法，再用动态规划统计所有合法分拆。

做法

记每个不同值的出现次数为 $c_x$。把候选多重集按非增顺序写成 $b_1\ge b_2\ge\cdots\ge b_k>0$。它可实现当且仅当

对所有 $i$ 成立，且 $\sum b_j=n$。这是二分图度数序列的 Gale–Ryser 条件。

子任务 1：枚举整数分拆

递归枚举 $n$ 的所有非增整数分拆，逐个检查上述前缀约束。$n\le20$ 时足够快。

子任务 2：三次动态规划

状态 $f[s][v]$ 表示已经选出的若干部分总和为 $s$，最后一个部分为 $v$ 的方案数。加入新部分 $x\le v$，并要求新前缀和不超过对应的 $L_i$。直接枚举 $v,x$，复杂度为 $O(n^3)$。

子任务 3：后缀和优化

固定新总和 $s$ 与新末项 $x$ 时，前一末项可以是任意不小于 $x$ 的值。因此预处理

即可用一次查询完成转移。第 $i$ 个部分不超过 $n/i$，有效状态总数为 $O(n^2\log n)$。

正确性证明

引理 1 候选大小序列 $b$ 可实现当且仅当满足所有 Gale–Ryser 前缀约束。

证明：建立二分图，左侧每个不同值的度数为其出现次数，右侧每个最终集合的度数为集合大小，边表示该值被放入该集合。简单二分图恰好保证集合内不重复。Gale–Ryser 定理给出的充要条件正是上述不等式。

引理 2 动态规划恰好枚举所有满足约束的非增整数分拆一次。

证明：状态记录总和与最后一项，转移只加入不大于末项的正整数，所以每个非增分拆有唯一生成路径；每一步同时检查相应前缀上界，所以只保留且保留全部合法分拆。

定理 算法输出可构造多重集的数量。

证明：由引理 1，可构造多重集与合法非增分拆一一对应；由引理 2，动态规划对它们各计数一次。

复杂度

子任务 1 复杂度为整数分拆数量乘 $O(n)$。子任务 2 时间复杂度为 $O(n^3)$。满分算法时间复杂度为 $O(n^2\log n)$，空间复杂度为 $O(n^2)$。