CF2225D Exceptional Segments

· · 题解

简单题。

题意

考虑一个 [1,2,3,\dots,n] 的序列和数 x，你需要找到有多少个数对 (l,r) 使得：

## 解法 以下令 $S_i=\bigoplus_{j=1}^{i} j$。 经典结论： - $n\bmod 4=0\Longleftrightarrow S_n=n

证明？我不会，不过你手动模拟也是能得出来的。

容易得出题目实际上是说有多少个 (l,r) 满足 S_l\oplus S_r=0，即 S_l=S_r。根据上面的性质，只有当 n\bmod4=1 和 n\bmod4=3 的时候才会满足题目条件。所以我们只需要找到 x 的左边和右边有多少个数满足题目条件即可。

答案就是左边的答案乘右边的答案，然后两个条件的答案相加。

记得取模。

AC submission.