JZOJ – 100035 区间

Time Limit : 2000ms
Memory Limit : 256MB

Description

Input

Output

Sample Input

Case 1

4 2 10
5 1 1 10

Case 2

1000 97 96998351
41 1668 505 2333

Sample Output

Case 1

4

Case 2

1749769

Data Constraint

解题思路

对于 $P$ 是质数的情况，我们可以考虑处理出长度为 $k$ 的数组，然后在 $j$ 向后移动的过程中，乘以前一个元素的逆元，在乘以新进入区间的数，可以获得一半的分数

但是本题数据较水，如果通过简单枚举 $j$ 并直接将以 $j$ 开头的每一个元素暴力乘起来，可以获得60分

我们可以考虑将数组以 $k$ 的长度分为若干个块，对于每一个块内统计前缀乘积和后缀乘积

如果查询串 $[l, r]$ 横跨两个块，那么我们可以用 $l$在前一个块的后缀乘积乘上 $r$ 在后一个块的前缀乘积

最后取模异或即可

代码

#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;
}