#22391: 簡單題-AC

#### jayw711kb@gmail.com (Jay Huang)

School : 國立虎尾科技大學
ID : 119439
2020-09-15 15:55:19
e359. Xor 運算(簡單! ~ :)) -- | From: [27.52.10.0] | Post Date : 2020-08-29 11:18

１）特性：

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

２）找規律：

ans=x1;

x1->1+0

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

x1->1

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

x1->1+2+1

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;

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

//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);

}

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

，所以一定不需要mod　1000000007

ZeroJudge Forum