Ahmed 爷爷的礼物：题解

思路

使用 Erdős–Ginzburg–Ziv 定理：任意 $2m-1$ 个整数中，都能选出恰好 $m$ 个，使它们的和被 $m$ 整除。

先按班级人数从小到大处理，最后留下最大的班级。设当前班级人数为 $m$。从尚未分配的已有盒子中任取 $2m-1$ 个，由定理必能选出其中 $m$ 个分给当前班级；其余 $m-1$ 个盒子放回候选池。

为什么候选池总有至少 $2m-1$ 个盒子？因为班级按人数递增处理，除去当前班和最后的大班，其余尚未处理班级人数都不少于 $m$；同时最后一个班将使用新盒子，所以已有盒子中还为它保留 $s_{\max}-1\ge m-1$ 个位置。加上当前班所需的 $m$ 个，至少有 $2m-1$ 个盒子。

所有其他班处理完后，候选池中恰有最大班级人数减一的盒子。设它们的礼物和模该班人数为 $r$，购买一个含 $m-r$ 个礼物的盒子即可。这个数位于 $1$ 到 $m\le201$，满足题目范围。

做法

对每个非最后班，从候选池取出 $2m-1$ 个数，用 0/1 动态规划求“选了多少个、当前和模 $m$ 的余数”：

记录转移来源后，从 $dp[m][0]$ 回溯出所选盒子。选中的分给当前班，未选中的放回池中。

小规模可以枚举已有盒子的排列；中规模可以在盒子子集上维护当前班余数；满分算法使用上述 EGZ 定理和按班级独立的基数—余数 DP。

正确性证明

引理 1：处理人数为 $m$ 的非最后班级时，候选池至少有 $2m-1$ 个已有盒子。

当前班需要 $m$ 个盒子。最后的大班还需要从已有盒子中取得其人数减一个盒子，数量至少为 $m-1$。其他尚未处理班级只会增加候选池的必要数量。因此至少有 $m+(m-1)=2m-1$ 个。

引理 2：算法总能为每个非最后班级选出合法的 $m$ 个盒子。

由引理 1 可以取得 $2m-1$ 个候选盒子。根据 Erdős–Ginzburg–Ziv 定理，其中存在恰好 $m$ 个数之和被 $m$ 整除。动态规划枚举了所有指定基数的子集及余数，因此一定能找到并回溯该子集。

引理 3：算法为最后班级构造的新盒子合法。

前面每次恰好永久分配当前班人数个已有盒子，所以最后恰剩 $m-1$ 个已有盒子。令其和模 $m$ 为 $r$，加入 $m-r$ 后总和模 $m$ 为零；且 $1\le m-r\le m\le201\le10^6$。

定理：算法输出一个满足全部要求的分配方案。

由引理 2，每个非最后班恰得规定数量的互不重复已有盒子，且礼物和满足整除。由引理 3，最后班恰得剩余已有盒子和唯一新盒子，也满足整除。所有盒子被使用且仅使用一次，所以方案合法。

复杂度

每个班级人数为 $m$ 时，动态规划时间为 $O(m^3)$，空间为 $O(m^3)$（保留逐物品回溯状态）。总时间为 $O(n^3)$，空间为 $O(n^3)$；在 $n\le200$ 时满足要求。