(打表找规律+前缀异或和)MORE XOR-蒲公英云

(打表找规律+前缀异或和)MORE XOR

题目链接：https://nanti.jisuanke.com/t/38230

比赛的时候也在推规律，可惜手动推错了~再者推出来还要用前缀异或和来解决，不然时间复杂度太高，会TLE.

之前不知道用前缀异或和，首先做个小题目：（前缀异或和）51nod 2128 前缀异或

//队友写的打表代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int s[maxn],p[maxn]={0};
int f(int l,int r)
{
    int x=0;
    for(;l<=r;l++){
        x^=s[l];
        p[s[l]]++;
    }
    return x;
}
int g(int l,int r)
{
    int x=0;
    for(int i=l;i<=r;i++)
        for(int j=i;j<=r;j++)
            x^=f(i,j);
    return x;
}
int w(int l,int r)
{
    int x=0;
    for(int i=l;i<=r;i++)
        for(int j=i;j<=r;j++)
            x^=g(i,j);
    return x;
}
int main()
{
    freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,q;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i]);
        scanf("%d",&q);
        while(q--){
            int l,r;
            memset(p,0,sizeof(p));
            scanf("%d %d",&l,&r);
            //printf("%d\n",w(l,r));
            w(l,r);
            printf("q=%d ",20-q);
            for(int i=1;i<=n;i++)
                if(p[i])
                printf("%d:%d  ",i,p[i]%2);
            printf("\n");
        }
    }
    return 0;
}
/*
输入数据：
1
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
*/

打表可以看出是以4为周期的，0表示这个数不参与异或，1表示这个数要参与异或。

mod4余1:1000

mod4余2:1100

mod4余3:0100

mod4余0:0000

题目AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,q,l,r;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=5;i<=n;i++){
            a[i]^=a[i-4];   //因为答案是4为周期的，所以我们将mod4余数相等的相异或
        }
        scanf("%d",&q);
        while(q--){
            scanf("%d%d",&l,&r);
            int res=0;
            if((r-l+1)%4==1){
                res^=a[r];
                if(l>4) res^=a[l-4];  //1000
            }else if((r-l+1)%4==2){
                res^=a[r]^a[r-1];
                if(l>=3) res^=a[l-3];  //1100
                if(l>=4) res^=a[l-4];
            }else if((r-l+1)%4==3){   //0100
                res^=a[r-1];
                if(l>=3) res^=a[l-3];
            }
            printf("%d\n",res);
        }
    }
    return 0;
}