题解：P14470 [COCI 2025/2026 #1] 松鼠 / Zagi

happybob · 2025-11-10 07:44:14 · 题解

问题是公平组合游戏，考虑计算 SG 函数。注意到任意时刻每个序列对应原序列的一个区间，所以记 f_{l,r} 表示区间 [l,r] 的 SG 函数，每次枚举删除的数 x 并由此将 [l,r] 划分为若干子区间，计算子区间游戏的 SG 函数的 \mathrm{XOR}，并所有 x 求结果的 \mathrm{MEX} 即可。至此不难得到一个关于 n 的多项式复杂度算法。

考察计算 SG 函数的递归形式，可以发现在递归计算时，有大量 [l,r] 区间满足 a_{l-1}=a_{r+1} 且 a_{l-1} 没有出现过在 [l,r] 的任何位置。这种区间显然只有 O(n) 个。如果能计算出这些区间的答案，那么我们猜测原问题也能得以更高效地计算。

实际上并非如此。就算能计算上述 O(n) 种区间，我们考虑要计算任意区间 [l,r] 时，枚举 x 并划分开成子区间的问题中，尽管中间的大部分区间都是这样的区间，但是考虑区间内第一个 x 的位置 i，则你发现 [l,i) 并非一个这样的区间，同理最后一个位置加 1 到 r 的这段后缀也没有得以预先计算。考虑这样区间的形态，不难发现 i 是 [l,n] 中 a_i 的首次出现位置。故我们考虑将形如这样的区间也预先计算答案，即对于每个 i，之前和之后每种数第一次出现位置之前的答案。这样的区间总共有 O(nV) 个。如果能预先计算这些答案，就能求解任意区间的答案。而计算这样的区间答案只需要按照区间右端点从小到大按照同样方法计算即可。对于区间异或问题，由于按照右端点从小到大计算了，所以实则可以 O(1) 计算区间异或，这样复杂度应该是 O(nV^2) 的。