队友手速惊人，秒杀 1001 和 1012(-1)。

本来以为 1006(-1) 需要线段树二分哈希，没想到 $n\le10^4$，暴力扫就行了。要注意单个字符不是合法串，吃一发。

1010 是 tarjan+dfs，是队友写的。

1009(-1) 由于异或不满足分配率，做不了一点。
注意到里面带 $2^k,4^k$，因此当 $k$ 足够大时乘法分配率展开的四项会被 $2^k,4^k$ 分开，其异或互相不影响。
因此，当 $k$ 较大时，可以把四项异或后的结果单独求出，然后再加起来，其中四项分别是

  • $\bigoplus\limits_{i=1}^{p-1}\operatorname{inv}(i)i=1\oplus(p-1)^2$
  • $\bigoplus\limits_{i=1}^{p-1}\operatorname{inv}(i)4^k=4^k\bigoplus\limits_{i=1}^{p-1}i$
  • $\bigoplus\limits_{i=1}^{p-1}2^ki=2^k\bigoplus\limits_{i=1}^{p-1}i$
  • $\bigoplus\limits_{i=1}^{p-1}8^k=0(p\ne2)$

其中第一个式子成立是因为当 $i^2\ne1$ 时，逆元一一对应，每个数与其逆元的乘积异或后相互抵消，除了 $i=1$ 和 $i=p-1$。
第二个式子成立使用了逆元一一对应性。
第四个式子成立是因为当 $p\ne2$ 时，由于 $p$ 是质数，所以 $p-1$ 是偶数，所以互相抵消了。

求答案还需要求出 $f(n)=\bigoplus\limits_{i=1}^ni$。
注意到 $4i,4i+1,4i+2,4i+3$ 的异或和为零，因此

  • 当 $n=0\pmod 4$ 时，$f(n)=n$。
  • 当 $n=1\pmod 4$ 时，$f(n)=1$；
  • 当 $n=2\pmod 4$ 时，$f(n)=n+1$；
  • 当 $n=3\pmod 4$ 时，$f(n)=0$；

当 $k$ 较小时，答案可以用 __int128_t 存下，此时 $p8^k<2^{127}$，在 $p\le3000$ 时满足。
当 $k$ 较大时，四项互不干扰，此时 $2^k>p^2$，在 $p>3000$ 时满足。
算 $1\oplus(p-1)^2$ 时忘记开 __int128_t 了，白吃一发。

最后是神秘签到题计算几何 1005(-1)，结果发现没人会写计算几何。
我只知道答案是相邻 3 个点判一下共线，被顺时针逆时针以及内外绕晕了。

  • 判断顺时针逆时针可以取出最高点，然后使用其相邻两点的叉积正负来判断。
  • 判断内外得记录是否绕过一圈。

感恩队友写出来了，我不用写了！