---

 

解題思路：

用位元互斥或(bitwsie_xor ,^)的定義和特性並找規律，由數學歸納法整理出公式

還有可以邊讀邊算

 

提示：

１）特性：

let a1,a2,a3 is a real number, b1,b2,b3 is a boolean type.

交換性:

a1^a2^a3=a1^a3^a2;

b1^b2^b3=b1^b3^b2;

 

自滅性：

a1^a1=0;

 

原本性：

a1^0=a1;

 

重複性：（奇數次便會重複性）

a1^a1^a1=a1;

更多請參見：

https://geeksforgeeksjay.blogspot.com/2020/08/blog-post.html

２）找規律：

要是Ｎ＝１，則集合是｛x1｝

ans=x1;

x1->1+0

要是Ｎ＝１，則集合是｛x1,x2｝

ans=x1^x2^(x1^x2);

x1->1

要是Ｎ＝３，則集合是｛x1,x2,x3｝

ans=(X1^X2^X3^(X1^X2)^(X2^X3)^(X1^X3)^(X1^X2^X3))%(1000000007)

x1->1+2+1

要是Ｎ＝4，則集合是｛x1,x2,x3,x4｝

ans=(X1^X2^X3^x4^(X1^X2)^(X1^X3)^(X1^X4)^(x2^x3)^(x2^x4)^(x3^x4)^(X1^X2^X3)^(X1^X2^X4)^(X1^X3^X4)^(X2^X3^X4)^(X1^X2^X3^x4))%(1000000007)

x1->1+3+2+1

 

所以公式是：

time=1+(N-1)+(N-2)+...+2+1=1+(N-1)*(N-1+1)*(N-1)/2=1+(N-1)*(N-1)*N/2;

 

由１）和２）可知：

要是time是偶數，ans=０,time 為奇數ans=x1^x2^...^xn;

片段程式碼：

//先判斷再輸入並做運算沒有比較快（如方法２）

//method 1

 

//AC (68ms, 72KB)

　　　　　xor_times=1+N*(N-1)*(N-1)/2;

int val;

scanf("%d",&val);

int tmp=val;

for(int i=1;i<N;i++)

{

scanf("%d",&val);

tmp^=val;

}

if(xor_times%2==0)printf("0\n");

 

else printf("%d\n",tmp);

 

//method 2

 

//AC (74ms, 96KB)

 

　　　　int val=0,tmp=0;

xor_times=1+N*(N-1)*(N-1)/2;

if(xor_times%2==0)

{

printf("0\n");

                        //讀完剩下的值，不然接下來的一筆測資會有問題

for(int i=0;i<N;i++)scanf("%d",&val);

}

else

{

int val;

scanf("%d",&val);

int tmp=val;

for(int i=1;i<N;i++)

{

scanf("%d",&val);

tmp^=val;

}

printf("%d\n",tmp);

 

}

 

還有你有沒有發現不尋常之處？

 

 

其實沒有不尋常之處

因為第一行一個整數N(N<=10^5)和集合x｛x1,x2,..,xn｝皆小於Ｎ

，所以集合ｘ一定皆小於1000000007，答案一定在０和1000000007之間

，所以一定不需要mod　1000000007