自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:32:39，当前版本为作者最后更新于2021-07-28 16:14:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门。

题意简述：给出 $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$ 表示检查的复杂度。

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

• 把 vector 换成链式前向星。
• 使用 fread。
• 检查时使用指针而不是数组。
• 如果已经不符合条件，退出检查（不加这个优化会 T 掉几个点）。

#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;
}