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