题解

思路

计数框架

先放入若干个值不超过 $29$ 的“低值游戏”，用背包计算

$$f(s)=\#\{S:\sum_{i\in S}a_i=s\}\qquad(0\le s\le60).$$

以后加入的游戏都取 $31$ 到 $60$。两个这样的高值之和已经超过 $60$，所以一个礼包至多含一个高值游戏。若加入一个值为 $60-s$ 的游戏，它恰好贡献 $f(s)$ 个新礼包。因此最终礼包数精确等于

$$f(60)+\sum_{x\text{ 为加入的高值游戏}}f(60-x).$$

这把构造问题转化为：先制造一组面额 $f(0),f(1),\ldots,f(29)$，再用至多剩余数量的高值游戏表示目标差值。

做法

子任务 1

当 $m\le60$ 时，直接放入 $m$ 个值为 $60$ 的游戏。任何合法礼包只能选择其中一个游戏，所以恰有 $m$ 个礼包。

子任务 2

先放入 $18$ 个值为 $1$ 的游戏。此时

$$f(s)=\binom{18}{s}\quad(0\le s\le18).$$

把这些二项式系数看成无限背包的硬币面额。令 $dp_x$ 表示拼出 $x$ 所需的最少硬币数，并记录最后使用的面额。由于 $f(0)=1$，每个目标一定可达。

对整个有限值域 $0\le x\le500000$ 逐项递推可得 $dp_x\le42$。因此恢复出的高值游戏不超过 $42$ 个，加上开头的 $18$ 个游戏，总数不超过 $60$。该有限值域上界也由证据程序完整重算，而不是只抽样检查。

满分算法

反复进行以下一次尝试：

1. 随机选择上界 $L\in[1,29]$，不断随机加入 $[1,L]$ 中的低值游戏，并维护 $f$。
2. 若再加入当前游戏会使 $f(60)>m$，就停止加入低值游戏。
3. 令余量 $r=m-f(60)$。将 $f(0),f(1),\ldots,f(29)$ 从大到小贪心使用；使用一次 $f(s)$ 就加入一个值为 $60-s$ 的高值游戏。
4. 若在总游戏数不超过 $60$ 时把 $r$ 减到零，则输出；否则重新尝试。

随机低值背包通常产生近似几何增长的一组面额，因此贪心表示所需项数很少。算法是 Las Vegas 型：失败的尝试不会输出，只有余量被精确减为零时才输出。实现固定伪随机数种子以便确定性重建；独立实现使用另一种随机数生成器。正式范围内的广泛差分、边界压力和检查器重计数共同验证构造。

正确性证明

任意两个高值游戏的和大于 $60$，所以礼包不可能含两个高值游戏。不含高值游戏的礼包共有 $f(60)$ 个；含某个值为 $x$ 的高值游戏时，其余低值游戏必须凑成 $60-x$，共有 $f(60-x)$ 种选择。不同高值游戏按下标区分，贡献可以直接相加。因此计数公式无重无漏。

子任务 1 的每个礼包恰为一个值为 $60$ 的单元素子集，数量为 $m$。

子任务 2 中，值为 $60-s$ 的每个高值游戏贡献 $\binom{18}{s}$。最短路式完全背包恢复的面额和恰为 $m$，故总礼包数恰为 $m$；全值域递推保证总游戏数不超过 $60$。

满分算法只在贪心面额和恰为 $m-f(60)$ 时输出。代入计数公式，输出方案的礼包数必为 $m$；长度和值域在输出前也都满足限制。因此算法输出的任何方案均合法。

复杂度分析

子任务 2 的时间复杂度为 $O(19m)$，空间复杂度为 $O(m)$。

满分算法每次尝试维护长度为 $61$ 的背包，时间复杂度为 $O(60^2)$，空间复杂度为 $O(60)$；总耗时再乘实际尝试次数。