2015多校連合第5場hdu 5344 MZL's xor

Problem Description
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
 
Input
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
 
Output
For every test.print the answer.
 
Sample Input

   
   
   
   

    
    
    
    2
3 5 5 7
6 8 8 9
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    14
16
   
   
   
   

 
この问题ですか?データ量が少なくないAC率が低いわけではありません说明は难しくありませんが、瞑想しない结果は加算する时にn*nの等式が异なったり、手动シミュレーションを操作したりして演算量が大きすぎることを発见しましたが、A[i]+A[j]がA[j]+A[i]をもう一度计算する必要があることを再现しました.これで私たちは和を求める必要はありません.ただ、A[1]~A[n]を1つずつ計算するだけで、2を乗じたことを覚えています.コードが受け入れられないほど短い

#include <iostream>
#include<cstdio>
using namespace std;
long long n,m,z,l,k,a,t;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld",&n,&m,&z,&l);
        k=0,a=0;
        for(int i=1;i<n;i++)
        {
            k=(k*m+z)%l;
            a^=(2*k);
        }
        printf("%lld
",a);
    }
    return 0;
}