题解

思路推导

先用背包判断原数组能否被等和划分。若总和为奇数，或不存在和为总和一半的子集，原数组已经是好的，答案为 $0$。

若可以划分，则答案一定为 $1$。不断把所有元素同时除以 $2$，直到至少有一个元素为奇数。删除任意一个此时为奇数的元素后，剩余总和为奇数，必然不能等和划分。等价地，直接删除原数组中二进制末尾零个数最少的元素。

做法

使用位集背包：初始只有和 $0$ 可达，对每个 $a_i$ 执行 dp |= dp << a_i。若总和一半不可达则输出 $0$；否则找到 $v_2(a_i)$ 最小的下标并输出删除该元素。

小规模可以枚举所有子集，并逐个尝试删除元素。中等规模可以为每个候选删除下标重新做一次普通布尔背包。正式做法利用二进制估值结论，只需一次背包。

正确性证明

背包准确判断是否存在元素和为总和一半的子集，因此准确判断原数组是否已经是好数组。

若原数组可等和划分，则总和为偶数。令 $2^k$ 是所有元素共同含有的最大二次幂因子。全部元素除以 $2^k$ 后，总和仍为偶数，且至少一个元素为奇数。删除这样的奇数后剩余总和为奇数，不可能分为两个整数和相等的子序列。因此删除一个元素足够；而原数组并不好，所以不能删除零个，最优值正是一。该奇数对应原数组中二进制末尾零最少的元素，算法输出的下标合法且最优。

复杂度分析

设 $S=\sum a_i$。位集背包时间复杂度为 $O(nS/w)$，空间复杂度为 $O(S)$，其中 $w$ 为机器字长。