# JZOJ – 100035 区间

Time Limit : 2000ms
Memory Limit : 256MB

4 2 10
5 1 1 10

1000 97 96998351
41 1668 505 2333

4

1749769

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;
const int MAXN = 20000000 + 10;

int data[MAXN];
int f[MAXN], g[MAXN];

int n, k, p;
int a, b, c, d;

int block_num;
long long ans = 0;

inline int blo(int x){
return (x-1) / k + 1;;
}

int main(){

freopen("range.in", "r", stdin);
freopen("range.out", "w", stdout);

scanf("%d%d%d", &n, &k, &p);
scanf("%d%d%d%d", &a, &b, &c, &d);

data[1] = a;
for(register int i=2; i<=n; i++){
data[i] = (((long long)data[i-1] * b) % d + (long long) c) % d;
}

int last = -1;

for(register int i=1; i<=n; i++){
if(blo(i) == last){
f[i] = ((long long)f[i-1] * data[i]) % p;
}else{
f[i] = data[i] % p;
last = blo(i);
}
}

last = -1;
for(register int i=n; i>=1; i--){
if(blo(i) == last){
g[i] = ((long long)g[i+1] * data[i]) % p;
}else{
g[i] = data[i] % p;
last = blo(i);
}
}

for(register int i=1; i<=n-k+1; i++){
int j = i + k - 1;

if(blo(i) == blo(j))
ans ^= f[j];
else{
int tmp = ((long long)g[i] * f[j]) % p;
ans ^= tmp;
}
}

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

return 0;
}