题解：AT_arc102_c [ARC102E] Stop. Otherwise...

happybob · 2026-08-11 10:48:56 · 题解

对固定的 i，考虑 i 是否为偶数，如果是偶数限制 \dfrac{i}{2} 至多选一个，否则没有这个限制。

除去这个限制外，考虑所有 a+b = i 的二元对，彼此不交，每个限制 c_a\times c_b=0，我们枚举有 j 个二元对 (a,b) 满足 c_a + c_b \neq 0，也就是 a 或 b 选了，并钦定其余二元对 c_a+c_b=0，贡献有个系数 2^j 表示每个选了的二元对其实是选的 a 还是 b，还有一个 \dbinom{w}{j}，w 是总二元对个数。对于不在任何二元对里的数没有额外限制，然后问题变为 x_1+x_2+\cdots + x_m=n 的序列个数，有若干数要求 \geq 1，也就是 j 个二元对的值，其他的 \geq 0，简单插板即可。直接实现就是 O(n^2)，不需要容斥或 DP。