题解：AT_arc214_c [ARC214C] Divide into 4 Teams

ran_qwq · 2026-02-10 16:41:54 · 题解

结论：设 S 为和为 \sum P_i 的一半的子集数量，答案为 S^2-2S。

令集合 X=A\cup C，Y=B\cup C。转化为选择 X,Y，要求 C=X\cap Y、A=X-Y、B=Y-X、D=U-X-Y 均非空且 X,Y 的和均为 \sum P_i 的一半。

考虑总方案数减去不合法方案数。总方案数是 S^2，其中 S 可以用背包 dp O(n\sum P_i) 求出。对于一个 X，有且仅有 Y=X 和 Y=U-X 这两种情况是不合法的。所以答案是 S^2-2S。

这是代码。