#include <iostream>
using namespace std;
typedef long long LL;

int main()
{
    LL t;
    cin >> t;
    LL n;
    for (int i = 0; i < t; i++){
        cin >> n;
        LL yu = n % 4;  //找规律，找到问题以4为循环规律节点
        if (yu == 0) cout << n << endl;  //四个情况
        else if (yu == 1) cout << 0 << endl;
        else if (yu == 2) cout << n + 1 << endl;
        else cout << 1 << endl;
    }

    return 0;
}

咳咳，本人第一次写博客，有问题请指正哈😁

下面，我们来分析这道题吧！

当你看到了图和最短路时，是否脑子一热：我会，djikstra和spfa嘛。但是定睛一看，完全图和 n (1≤n≤2×10^9) 显然，这不是搜索题。所以，这题没办法套用模板，找规律吧！

咋找呢？

我们先读题，再看示例解析（我相信看这篇文的大部分人是没有明白题要干嘛的）

对于第二组测试数据，从 1 号点出发到 2 号点只能走 1→2 这条边，因此 d2 = 3，而又因为 d1= 0，因此输出的 S=d1​⊕d2​=0⊕3=3。

嘛，发现没？ 1 -> 1 是有路的！ 所以：

S = 所有d的异或 = （1⊕1）⊕（1⊕2）⊕（1⊕3）···（1⊕n）= （1⊕1···1⊕1）⊕（1⊕···i···⊕n）<n个1，i属于n>

所以，我们只需要知道前面（1⊕1···1⊕1）是多少，再和后面（1⊕···i···⊕n）异或就行了！

我们知道，2m+1个 1 的异或为 1， 2m个1的异或为0，所以，前面解决！那后面咋办？

有些同学可能会想：用数组？但是数组太大了！而且访问没有规律，这个不行！有没有时间空间都是O(1)的方案呢？有！我们看这段代码：

#include<iostream>
using namespace std;

int main() {
	int sum = 1;
	for (int i = 2; i <= 20; i++) {  //输出前20个找早规律
		sum ^= i;
		cout << sum <<"  " << i << endl;  // 异或   n
	}
	return 0;
}

3  2
0  3
4  4
1  5
7  6
0  7
8  8
1  9
11  10
0  11
12  12
1  13
15  14
0  15
16  16
1  17
19  18
0  19
20  20

发现没？当 n%4 = i， i =1 -> result = 1, i = 2 -> result = n + 1 , i = 3 -> result = 0, i = 0 -> result = n ! 那么，规律就出来啦！只需要条件判断就行了！

AC代码放在开头了，谢谢！