题目链接:https://ac.nowcoder.com/acm/problem/205370
题目难度:提高+/省选-
推荐理由:思路非常妙,巧妙的运用了随机生成数据的特点,一道非常好的思维题
题目知识点:位运算技巧,阈值思想
题意描述:我们用一种随机生成数据的方式生成一个长度为n的序列,然后有m个询问,每次询问序列中是否存在和当前这个数xor以后二进制中1的个数小于等于3

这题如果不是随机的,可能不太可做。
但是然后运用了随机的这个思想,我们考虑随机分布基本上是平均的,可以根据生日悖论推导一下。
于是我们还有一种阈值的考虑方法,如果把他拆掉,拆成4个部分,每个部分是一个1<<16的范围是不是更方便我们处理?
紧接着我们发现了一个非常巧妙的性质,如果一个数和它xor以后,二进制中1的个数小于等于3,那么这四个部分一定有一个部分是和这个数完全相同的,抽屉原理可以证明,这个3设的非常巧妙。
那么我们查找的时候是不是就可以找到所有和这个部分相同的数,然后暴力check,因为数据是随机的,所有这部分需要暴力的数不会太多,可以接受。
我们接着这个想法,把每个数拆成四份,然后插在vector里面,然后每次暴力在vector里面查询即可!
需要注意的是我们实现的时候这个二进制中1的个数不能直接用__builtin_popcount,因为是ULL范围内的,我们还是要把它拆成四份分开算,当然你也有其他的办法也可以!

代码:

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pb push_back
using namespace std;
const int N=1e6+5,S=(1<<17),P=998244353;
int n,m,pw[N],ans;ULL a[N],B;
vector<ULL>v[4][S];
ULL G(ULL x){x^=x<<13;x^=x>>7;x^=x<<17;return x;}
ULL calc(ULL x){
    int res=0;
    for(int i=0;i<4;i++)res+=__builtin_popcount(x&B),x>>=16;
    return res;
}
void insert(ULL x){
    ULL t=x;
    for(int i=0;i<4;i++)v[i][x&B].pb(t),x>>=16;
}
bool ask(ULL x){
    ULL t=x;
    for(int i=0;i<4;i++){
        for(auto y:v[i][x&B])if(calc(t^y)<=3)return true;
        x>>=16;
    }
    return false;
}
int main(){
    scanf("%d%d%llu",&n,&m,&a[0]);B=(1<<16)-1;
    for(int i=1;i<n;i++)a[i]=G(a[i-1]);
    for(int i=0;i<n;i++)insert(a[i]);
    pw[0]=1;for(int i=1;i<=m;i++)pw[i]=pw[i-1]*2%P;
    for(int i=0;i<m;i++){
        ULL x;scanf("%llu",&x);
        if(ask(x))ans=(ans+pw[m-i-1])%P;
    }
    printf("%d\n",ans);
    return 0;
}