P7738 [NOI2021] 量子通信

FxorG · 2021-07-29 22:59:37 · 个人记录

考虑 k 很小，可以从上面入手。

当串被划分成 k+1 个段时，一定至少有一个完全相同,实际上就是鸽巢原理。

考虑到这点以后将 256 长度的串划分为 16 段即可，预处理出第 i 段 串是 j （二进制下）的串下标。

然后枚举相同的段 [0,15] ，对相同的段遍历每个串，然后 xor 得到翻转的个数。

卡常：

1. 快读快写
2. vector 换 basic_string

\text{Code}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <cctype>
#include <cstdlib>

#define ll long long
#define il inline
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar()  (sp == ep && (ep = (sp = ibuf) + fread(ibuf,1,mm,stdin),sp == ep) ? EOF : *sp++)
#define putchar(x) ((op-obuf<mm) ? (*op++=x) : (fwrite(obuf,op-obuf,1,stdout),op=obuf,*op++=x))
const int mm = 1<<20;
static char ibuf[mm],obuf[mm],*sp=ibuf,*ep=ibuf,*op = obuf,*p3 = obuf;
using namespace std;
typedef unsigned long long ull;
const int N = 400000;
bool s[N+1][256];

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

il void gen(int n, ull a1, ull a2) {
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 256; ++j)
            s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}
il int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
il ull urd() {
    ull f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
void pr(ull x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

#include <bitset>
basic_string<int>g[16][65537];
bitset<256>B[N+1],Q;
bool qstr[256];
char str[65];
ull a1,a2; bool las_ans;
int n,m,kk;

il void init() {
    char ch=getchar();
    while(!isdigit(ch)&&(ch>'F'||ch<'A')) ch=getchar();
    int tot=0;
    while(isdigit(ch)||(ch<='F'&&ch>='A')) str[tot++]=ch,ch=getchar();
    kk=rd();
    for(int i=0;i<64;++i) {
        ch=str[i];
        if(ch=='0')      qstr[(i<<2)]=0,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=0;
        else if(ch=='1') qstr[(i<<2)]=0,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=1;
        else if(ch=='2') qstr[(i<<2)]=0,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=0;
        else if(ch=='3') qstr[(i<<2)]=0,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=1;
        else if(ch=='4') qstr[(i<<2)]=0,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=0;
        else if(ch=='5') qstr[(i<<2)]=0,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=1;
        else if(ch=='6') qstr[(i<<2)]=0,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=0;
        else if(ch=='7') qstr[(i<<2)]=0,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=1;
        else if(ch=='8') qstr[(i<<2)]=1,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=0;
        else if(ch=='9') qstr[(i<<2)]=1,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=1;
        else if(ch=='A') qstr[(i<<2)]=1,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=0;
        else if(ch=='B') qstr[(i<<2)]=1,qstr[(i<<2)+1]=0,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=1;
        else if(ch=='C') qstr[(i<<2)]=1,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=0;
        else if(ch=='D') qstr[(i<<2)]=1,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=0,qstr[(i<<2)+3]=1;
        else if(ch=='E') qstr[(i<<2)]=1,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=0;
        else if(ch=='F') qstr[(i<<2)]=1,qstr[(i<<2)+1]=1,qstr[(i<<2)+2]=1,qstr[(i<<2)+3]=1;
    }
    if(las_ans) {
        for(int i=0;i<256;++i) qstr[i]^=1;
    }
}

int main() {
//  freopen("qi.in","r",stdin); freopen("qi.out","w",stdout);
    n=rd(); m=rd(); a1=urd(); a2=urd();
    gen(n,a1,a2);
    for(int i=1;i<=n;++i) {
        for(int j=0;j<16;j++) {
            int qwq=0;
            for(int k=(j<<4);k<(j<<4)+16;k++) B[i][k]=s[i][k],qwq=(qwq<<1)+s[i][k];
            g[j][qwq]+=i;
        }
    }
    while(m--) {
        init();
        for(int i=0;i<256;i++) Q[i]=qstr[i];
        for(int i=0;i<16;++i) {
            int qwq=0; las_ans=0;
            for(int j=(i<<4);j<(i<<4)+16;++j) qwq=(qwq<<1)+qstr[j];
            for(int j=0;j<g[i][qwq].size();++j) {
                if((Q^B[g[i][qwq][j]]).count()<=kk) {
                    las_ans=1; break;
                }
            }
            if(las_ans) break;
        }
        putchar(las_ans?'1':'0'); putchar('\n');
    }fwrite(obuf,op-obuf,1,stdout);
    return 0;
}