P7738 [NOI2021] 量子通信

· · 题解

题目传送门。

题意简述：给出 n 个 256 位二进制数（随机生成）a_i。对于 m 个询问，每次给出一个 256 位二进制数 x 和一个十进制数 k，求是否存在 a_i 使得 x,a_i 不同位数个数不大于 k。

注意到这个 k\leq 15，一定是本题的突破点。再根据 16^2=256 与抽屉原理，不难想到将 256 位的二进制数看成 16 位的 65536 进制数。这样一来，如果 x 与 a_i 在二进制下不同位数个数不大于 15，那么它们在 65536 进制下必定至少有一位完全相等。这是显然的。

因此，我们可以枚举 x 在 65536 进制下的 16 位，并检查与 x 在该位相等的所有 a_i 是否符合要求。由于数据随机生成，所以某一位为某个数的 a_i 的期望个数为 \dfrac{n}{65536}\approx 7。所以对于每一位，我们期望检查 7 个 a_i 是否符合要求。而满足在 65536 进制下第 b 位为 c 的 a_i 的所有 i 可以开 vector 存储。

检查方法很简单：要求出 65536 进制数 x,y 在二进制下有多少位不同，只需要预处理出 0\sim 65535 在二进制下 1 的个数，然后枚举 x,y 的每一位（一共 16 位），加上 它们在这一位的值的异或和 在二进制下 1 的个数即可。

极限数据下空间复杂度为 16n，期望时间复杂度为 m\times 16\times 7\times 16\approx 2\times 10^8，其中 m 表示询问个数，第一个 16 表示枚举的 16 位，7 表示与 x 在枚举的某一位的值相等的 a_i 的期望个数，而第二个 16 表示检查的复杂度。

为了卡常，可以进行以下优化：

#include <bits/stdc++.h>
using namespace std;

#define gc getchar()
#define mem(x,v) memset(x,v,sizeof(x))

typedef unsigned long long ull;
typedef unsigned short us;

namespace IO{
    char buf[1<<23],*p1=buf,*p2=buf;
    #ifdef __WIN32
        #define gc getchar()
    #else
        #define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
    #endif
    inline int read(){
        int x=0;char s=gc;
        while(!isdigit(s))s=gc;
        while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
        return x;
    }
} using namespace IO;

const int N=400000+5;
const int W=65536;
bool s[N][256],q[256];

ull myRand(ull &k1,ull &k2){
    ull k3=k1,k4=k2;
    k1=k4,k3^=(k3<<23),k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
void gen(int n,ull a1,ull a2){
    for(int i=0;i<n;i++)
        for(int j=0;j<256;j++)
            s[i][j]=(myRand(a1,a2)&(1ull<<32))?1:0;
}

struct EDGE{
    int cnt,hd[W],nxt[N],to[N];
    void add(int x,int y){nxt[++cnt]=hd[x],hd[x]=cnt,to[cnt]=y;}
}buc[16];

ull n,m,a1,a2;
us val[N][16],mp[W],qq[16];
int main(){
    cin>>n>>m>>a1>>a2,gen(n,a1,a2);
    for(int i=0;i<n;i++)
        for(int j=0;j<16;j++){
            for(int k=0;k<16;k++)
                val[i][j]+=s[i][j*16+k]<<k;
            buc[j].add(val[i][j],i);
        }
    for(int i=1;i<W;i++)mp[i]=mp[i>>1]+(i&1);
    for(int i=0,las=0,k;i<m;i++,mem(qq,0)){
        for(int j=0,vv=0;j<64;j++,vv=0){
            char s=gc;
            if(isdigit(s))vv=s-'0';
            else if(s>='A'&&s<='F')vv=10+s-'A';
            else {j--; continue;}
            for(int l=0;l<4;l++)q[j*4+l]=(vv>>3-l)&1;
        }
        bool ok=0; k=read();
        for(int j=0;j<16;j++)
            for(int l=0;l<16;l++)
                qq[j]+=(q[j*16+l]^las)<<l;
        for(int j=0;j<16;j++){
            for(int p=buc[j].hd[qq[j]];p;p=buc[j].nxt[p]){
                int it=buc[j].to[p],cnt=0;
                us *pval=val[it],*pq=qq;
                for(int l=0;l<16;l++,pval++,pq++){
                    cnt+=mp[(*pval)^(*pq)];
                    if(cnt>k)break;
                } if(cnt<=k){ok=1; break;}
            } if(ok)break;
        } cout<<(las=ok)<<'\n';
    }
    return 0;
}