小V的序列题解

题目链接：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;
}