MZL’s xor

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K
(Java/Others)
Total Submission(s): 310 Accepted Submission(s): 225

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 ( A i + A j )( 1 ≤ i , j ≤ n )
The xor of an array B is defined as B 1 xor B 2 …xor B n

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
A 1 = 0 , A i = ( A i − 1 ∗ m + z ) m o d l
1 ≤ m , z , l ≤ 5 ∗ 10 5 , n = 5 ∗ 10 5

Output

For every test.print the answer.

Sample Input

2 3 5 5 7 6 8 8 9

Sample Output

14 16

题意：求所有a[i]+a[j] 异或值，因为a[i]+a[j] 和a[j]+a[i] 会异或掉所以只需考虑a[i]+a[i]

代码：

#include <stdio.h>  
#include <ctime>  
#include <math.h>  
#include <limits.h>  
#include <complex>  
#include <string>  
#include <functional>  
#include <iterator>  
#include <algorithm>  
#include <vector>  
#include <stack>  
#include <queue>  
#include <set>  
#include <map>  
#include <list>  
#include <bitset>  
#include <sstream>  
#include <iomanip>  
#include <fstream>  
#include <iostream>  
#include <ctime>  
#include <cmath>  
#include <cstring>  
#include <cstdio>  
#include <time.h>  
#include <ctype.h>  
#include <string.h>  
#include <assert.h>  

using namespace std;

long long n, m, z, l;


int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld%lld%lld", &n, &m, &z, &l);
        long long ans = 0;
        long long tmp = 0;
        for (int i = 2; i <= n;i++)
        {
            tmp = (tmp *m + z) % l;
            ans ^= (2 * tmp);
        }
        printf("%lld\n",ans);
    }
    return 0;
}