题解：CF2225D Exceptional Segments
manboo
·
·
题解
本文提供一个前无古人后无来者的做法（如有雷同，当我没说）。
题目概述：
打表查找 $1\le l\le r\le 100$ 的区间 $\left[l,r\right]$ 异或和，猜出结论：区间 $\left[l,r\right]$ 的异或和为 $0$ 当且仅当 $l=1$ 且 $r=4\times k-1\left(k\in\mathbb{N}^+\right)$，或者 $l$ 为偶数且 $r=l+4\times k-1\left(k \in \mathbb{N}^+\right)$。结论将在本文末附上证明。
$l=1$ 是与 $l=0$ 等价的（因为任何数异或 $0$ 都是原数），把所有 $l=1$ 的情况转换为 $l=0$，则上述结论对本题可以转换为：区间 $\left[l,r\right]$ 的异或和为 $0$ 当且仅当 $l$ 为 $\left[0,x\right]$ 内的偶数，$r=l+4\times k-1$ 且 $x\le r\le n$。
解不等式 $x\le r\le n$，将 $r=l+4\times k-1$ 带入得到 $x\le l+4\times k-1\le n$，解得 $\left\lceil\frac{x-l+1}{4}\right\rceil\le k\le \left\lfloor\frac{n-l+1}{4}\right\rfloor$。
$k$ 取整数值的数量，即为 $r$ 的数量：$\left\lfloor\frac{n-l+1}{4}\right\rfloor-\left\lceil\frac{x-l+1}{4}\right\rceil+1$。
由于 $\left\lceil\frac{p}{q}\right\rceil=\left\lfloor\frac{p+q-1}{q}\right\rfloor$，因此 $\left\lceil\frac{x-l+1}{4}\right\rceil=\left\lfloor\frac{x-l}{4}\right\rfloor+1$，因此 $\left\lfloor\frac{n-l+1}{4}\right\rfloor-\left\lceil\frac{x-l+1}{4}\right\rceil+1=\left\lfloor\frac{n-l+1}{4}\right\rfloor-\left\lfloor\frac{x-l}{4}\right\rfloor$。
答案即为 $\sum\limits_{l=0,2\mid l}^x \left\lfloor\frac{n-l+1}{4}\right\rfloor-\left\lfloor\frac{x-l}{4}\right\rfloor$。
我们得到了一个 $O\left(x\right)$ 的做法！
看一眼数据范围 —— ~~跑路吧~~ 考虑优化。
由于 $l$ 为偶数，故设 $l=2\times t$，则答案即为 $\sum\limits_{t=0}^{\left\lfloor{\frac{x}{2}}\right\rfloor}\left\lfloor\frac{n-2\times t+1}{4}\right\rfloor-\left\lfloor\frac{x-2\times t}{4}\right\rfloor$。
- 当 $t$ 为偶数时，设 $t=2\times j$，则：
$$\begin{aligned}\left\lfloor\frac{n-2\times t+1}{4}\right\rfloor-\left\lfloor\frac{x-2\times t}{4}\right\rfloor&=\left\lfloor\frac{n-4\times j+1}{4}\right\rfloor-\left\lfloor\frac{x-4\times j}{4}\right\rfloor\\&=\left\lfloor\frac{n+1}{4}-j\right\rfloor-\left\lfloor\frac{x}{4}-j\right\rfloor\\&=\left\lfloor\frac{n+1}{4}\right\rfloor-\left\lfloor\frac{x}{4}\right\rfloor\end{aligned}$$
由于 $t$ 为偶数的情况有 $\left\lfloor\frac{\left\lfloor\frac{x}{2}\right\rfloor}{2}\right\rfloor+1=\left\lfloor\frac{x}{4}\right\rfloor+1$种，故此部分答案为 $\left(\left\lfloor\frac{x}{4}\right\rfloor+1\right)\times\left(\left\lfloor\frac{n+1}{4}\right\rfloor-\left\lfloor\frac{x}{4}\right\rfloor\right)$。
- 当 $t$ 为奇数时，设 $t=2\times j+1$，则：
$$\begin{aligned}\left\lfloor\frac{n-2\times t+1}{4}\right\rfloor-\left\lfloor\frac{x-2\times t}{4}\right\rfloor&=\left\lfloor\frac{n-4\times j-1}{4}\right\rfloor-\left\lfloor\frac{x-4\times j-2}{4}\right\rfloor\\&=\left\lfloor\frac{n-1}{4}-j\right\rfloor-\left\lfloor\frac{x-2}{4}-j\right\rfloor\\&=\left\lfloor\frac{n-1}{4}\right\rfloor-\left\lfloor\frac{x-2}{4}\right\rfloor\end{aligned}$$
由于 $t$ 为奇数的情况有 $\left\lfloor\frac{\left\lfloor\frac{x}{2}\right\rfloor-1}{2}\right\rfloor+1=\left\lfloor\frac{x-2}{4}\right\rfloor+1$ 种，故此部分答案为 $\left(\left\lfloor\frac{x-2}{4}\right\rfloor+1\right)\times\left(\left\lfloor\frac{n-1}{4}\right\rfloor-\left\lfloor\frac{x-2}{4}\right\rfloor\right)$。
注意！由于 c++ 的整除取整是向 $0$ 取整，如计算 $-1$ 除以 $2$ 时，会返回 $0$，所以当 $x=1$ 时，$\left\lfloor\frac{x-2}{4}\right\rfloor+1$ 会返回 $1$，但我们想要的是 $0$，因此还需要特判一手。
恭喜你！成功地把 $O\left(x\right)$ 的做法优化到了 $O\left(1\right)$！
下面是代码时间：
```c++
typedef long long ll;
typedef __int128 lint;
const lint mod=998244353;
int main()
{
for(int T=read();T;T--)
{
ll n=read(),x=read();
print(((lint)(x/4+1)%mod*((n+1)/4-x/4)%mod+(lint)(x==1?0:((x-2)/4+1))%mod*((n-1)/4-(x-2)/4)%mod)%mod),puts("");
}
return 0;
}
```
附上对结论“区间 $\left[l,r\right]$ 的异或和为 $0$ 当且仅当 $l=1$ 且 $r=4\times k-1\left(k\in\mathbb{N}^+\right)$，或者 $l$ 为偶数且 $r=l+4\times k-1\left(k \in \mathbb{N}^+\right)$”的证明：
设 $S\left(n\right)=1\oplus2\oplus\cdots\oplus n$，规定 $S\left(0\right)=0$。
已知 $S(n)$ 具有如下规律：$$S\left(n\right)=\begin{cases}n,&n\equiv0\pmod{4}\\1,&n\equiv1\pmod{4}\\n+1,&n\equiv2\pmod{4}\\0,&n\equiv3\pmod{4}\end{cases}$$
下面尝试利用异或的周期性简略证明该规律的正确性：
考虑连续四个整数 $4\times k,4\times k+1,4\times k+2,4\times k+3\left(k\in\mathbb{N}\right)$ 的异或和，不难发现其二进制下的最低两位分别为 $00,01,10,11$，它们的异或和为 $00$，而更高位是相同的，故 $\left(4\times k\right)\oplus\left(4\times k+1\right)\oplus \left(4\times k+2\right)\oplus\left(4\times k+3\right)=0$。
- 若 $n=4\times k$，即 $n\equiv0\pmod{4}$，则 $S(n)=4\times k=n$。
- 若 $n=4\times k+1$，即 $n\equiv1\pmod{4}$，则 $S(n)=\left(4\times k\right)\oplus\left(4\times k+1\right)=1$。
- 若 $n=4\times k+2$，即 $n\equiv2\pmod{4}$，则 $S(n)=\left(4\times k\right)\oplus\left(4\times k+1\right)\oplus\left(4\times k+2\right)=1\oplus n=n+1$。
- 若 $n=4\times k+3$，即 $n\equiv3\pmod{4}$，则 $S(n)=\left(4\times k\right)\oplus\left(4\times k+1\right)\oplus\left(4\times k+2\right)\oplus\left(4\times k+3\right)=n\oplus n=0$。
证毕。现在回到对结论的证明中。
区间 $\left[l,r\right]$ 的异或和即为 $S\left(r\right)\oplus S\left(l-1\right)$，当且仅当 $S\left(r\right) = S(l-1)$ 时，其值为 $0$。
设 $a=l-1$，则 $a\ge0$，条件 $S\left(r\right)=S(l-1)$ 即 $S\left(r\right)=S\left(a\right)$。下面分情况讨论：
- 当 $a=0$ 时，有 $l=1$，需要 $S\left(r\right)=0\Leftrightarrow r\equiv3\pmod{4}\Leftrightarrow r=4\times k-1\left(k\in\mathbb{N}^+\right)$。
- 当 $a\ge1$ 时，有 $l\ge2$，继续分情况讨论：
- 若 $a\equiv0\pmod{4}$，则 $S\left(a\right)=a$，需要方程 $S\left(r\right)=a$ 有解。方程有且仅有解为 $r=a$，证明：
- 当 $r\equiv0\pmod{4}$ 时，$S\left(r\right)=r$，此时 $r=a$。
- 当 $r\equiv 2\pmod{4}$ 时，$S\left(r\right)=r+1\not\equiv0\pmod{4}$，因此 $r+1\ne a$，方程无解。
- 其他余数下，$S\left(r\right)$ 为 $0$ 或 $1$，由于 $a\ge4$，故 $S\left(r\right)<a$，方程无解。
但是，$r=a=l-1<l$，不满足 $r\ge l$，故方程无解，即 $a\not\equiv0\pmod{4}\Leftrightarrow l\not\equiv1\pmod{4}$。
- 若 $a\equiv1\pmod{4}$，则 $S\left(a\right)=1$，需要方程 $S\left(r\right)=1$ 有解。不难证明，方程有且仅有解为 $r\equiv1\pmod{4}\Leftrightarrow r=1,5,9,\dots$。又由于 $r>a$，故 $r=a+4\times k=l+4\times k-1\left(k\in\mathbb{N}^+\right)$。此时 $a\equiv1\pmod{4}$ 意味着 $l=a+1$ 是偶数。
- 若 $a\equiv2\pmod{4}$，则 $S\left(a\right)=a+1$，需要方程 $S\left(r\right)=a+1$ 有解。方程有且仅有解为 $r=a$，证明：
- 当 $r\equiv2\pmod{4}$ 时，$S\left(r\right)=r+1$，则 $r+1=a+1$，得到 $r=a$。
- 其他余数下，同理可得方程无解。
这里又回到了 $a\equiv0\pmod{4}$ 的情况，故方程无解，即 $a\not\equiv2\pmod{4}\Leftrightarrow l\not\equiv3\pmod{4}$。
- 若 $a\equiv3\pmod{4}$，则 $S\left(a\right)=0$，需要方程 $S\left(r\right)=0$ 有解。不难证明，方程有且仅有解为 $r\equiv 3 \pmod{4}\Leftrightarrow r=3,7,11,\dots$。又由于 $r>a$，故 $r=a+4\times k=l+4\times k-1\left(k\in\mathbb{N}^+\right)$。此时 $a\equiv3\pmod{4}$ 意味着 $l=a+1$ 是偶数。
综上所述，区间 $\left[l,r\right]$ 的异或和为 $0$ 当且仅当 $l=1$ 且 $r=4\times k-1\left(k\in\mathbb{N}^+\right)$，或者 $l$ 为偶数且 $r=l+4\times k-1\left(k \in \mathbb{N}^+\right)$。