CF2043F Nim

Cute_Fish · 2026-11-10 19:16:37 · 题解

诈骗题。下文记 cnt_i 表示 i 在询问区间 [l,r] 内的出现次数，由于值域较小，容易做到 O(nV)-O(1) 得出 cnt_i。

对于一个询问 [l,r] 观察到：

• 若存在 a_i=0(i\in[l,r]) 则答案即 r-l,cnt_0。
• 若存在 i 使得 cnt_i\ge2 则答案即 r-l-1,\sum_{cnt_i\ge 2}\dbinom{cnt_i}{2}。

然后判掉这两种情况之后，每个数显然至多出现一次，直接设 f_{i,j},g_{i,j} 分别表示当前考虑到数 i，使得异或和为 0 最少要保留的数的个数和方案数。转移是平凡的，单次询问时间复杂度 O(V^2)。那么总复杂度即 O(nV+qV^2) 可以通过。