MZL loves xor very much.Now he gets an array A.The length of A is n.He wants to know the xor of all (Ai+Aj)(1≤i,j≤n) The xor of an array B is defined as B1 xor B2...xor Bn
Multiple test cases, the first line contains an integer T(no more than 20), indicating the number of cases. Each test case contains four integers:n,m,z,l A1=0,Ai=(Ai−1∗m+z) mod l 1≤m,z,l≤5∗105,n=5∗105
For every test.print the answer.
2 3 5 5 7 6 8 8 9
14 16
找到了规律就好办了，发现对称性，相同的数异或后等于0，所以最后剩下自身*2来异或，注意要用long long
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 #include<stdlib.h> 8 #include<map> 9 using namespace std; 10 #define ll long long 11 #define N 600000 12 ll n,m,z,l; 13 ll a[N]; 14 int main() 15 { 16 int t; 17 scanf("%d",&t); 18 while(t--){ 19 scanf("%I64d%I64d%I64d%I64d",&n,&m,&z,&l); 20 a[1]=0; 21 for(int i=2;i<=n;i++){ 22 a[i]=(a[i-1]*m+z)%l; 23 } 24 ll ans=0; 25 for(int i=1;i<=n;i++){ 26 ans=ans^(a[i]+a[i]); 27 } 28 printf("%I64d\n",ans); 29 } 30 return 0; 31 }
原文：http://www.cnblogs.com/UniqueColor/p/4799171.html
