模数子集和 题解

思路

只需关心所选元素之和对 $m$ 的余数。规模较小时可以枚举选择；一般情况下维护可达余数。特别地，$n\ge m$ 时由鸽巢原理必有答案。

做法

子任务 1：枚举子集

枚举 $1$ 到 $2^n-1$ 的所有非空选择，累加对应元素并检查模 $m$ 余数。

子任务 2：小模数 DP

维护 can[r] 表示是否存在非空子集的和模 $m$ 为 $r$。加入一个数时，既可单独选择它，也可把它接到旧的可达余数后。每轮使用旧数组转移，保证每个位置至多使用一次。

子任务 3：鸽巢原理与 DP

若 $n\ge m$，考察前 $m$ 个元素的 $m+1$ 个前缀和余数。若某余数为零，或两个前缀余数相同，它们之间的非空连续段之和被 $m$ 整除，因此直接输出 YES。

否则 $n<m\le1000$，执行余数 DP 的复杂度至多 $O(m^2)$。

复杂度

三个层级的时间复杂度分别为 $O(n2^n)$、$O(nm)$ 和 $O(m^2)$；空间复杂度分别为 $O(1)$、$O(m)$ 和 $O(m)$。

正确性证明

引理 1　余数 DP 在处理前 $i$ 个数后，恰好标记这些数的所有非空子集和余数。

证明　新可达余数要么只选第 $i$ 个数，要么由旧子集再加入它；反向也显然成立。使用旧数组保证不重复选择。∎

引理 2　若 $n\ge m$，必存在答案。

证明　前 $m$ 个数产生 $m+1$ 个含空前缀的前缀和。若有非空前缀余数为零即得答案；否则由鸽巢原理两个前缀余数相同，它们之差对应非空连续子段且能被 $m$ 整除。∎

定理　算法输出 YES 当且仅当存在所求非空子序列。

证明　$n\ge m$ 时由引理 2 必为 YES；否则由引理 1，can[0] 为真恰等价于存在模 $m$ 为零的非空子集。∎