问题本质

给定 $n$ 个长度为 $256$ 的 01 串（字典 $S$），以及 $m$ 次查询，每次给出一个 256 位 01 串 $y$ 和整数 $k$（$0 \le k \le 15$），问是否存在字典中的串 $s$ 使得 $s$ 与 $y$ 的汉明距离 $\le k$。

核心思路

由于 $k$ 很小（最多 15），直接遍历 $n$ 个单词计算汉明距离会超时。 这里采用分块 + 预索引的方法：

将 256 位分成 16 块，每块 16 位。

对每个单词 $s_i$，预计算它在 16 个块上的 16 位值（用 unsigned short 存储）。

对每个块 $j$，建立哈希表 vec[j][value] 存储所有在该块上值为 value 的单词索引。

查询时，对 $y$ 同样分成 16 块，对每一块 $j$，取出该块的值 $c_j$，在 vec[j][c_j] 中查找候选单词。

对每个候选单词，计算它与 $y$ 的汉明距离（利用预计算的块值异或后查 popcount 表加速），若 $\le k$ 则返回 1。

算法步骤

预处理

调用 gen 生成字典。

对每个单词 $s_i$，将其 256 位分成 16 块，每块 16 位，计算每块的整数值 num[i][j]。

将单词索引 $i$ 加入对应块和值的列表 vec[j][value]。

预处理 pcnt 数组用于快速计算 16 位整数的二进制中 1 的个数（popcount）。

查询处理

读入 64 个 16 进制字符，转为 256 位 01 数组 b。

读入 $k$。

根据上一次答案 lastans 对 b 进行异或解密。

计算 $y$ 的 16 个块的值 c[j]。

遍历 16 个块 $j$，对每个候选单词 $t$ 在 vec[j][c[j]] 中：

初始化 tot = 0

遍历 16 个块，计算 num[t][l] ^ c[l] 的 popcount 并累加到 tot

如果中途 tot > k 则提前退出

若 tot <= k 则返回 1

输出结果并更新 lastans。

复杂度分析

预处理：$O(n \times 16)$

查询：最坏情况每个块候选单词数可能较多，但期望情况下由于 $2^{16} = 65536$ 较大，每个 vec[j][value] 中单词数约为 $n / 65536$，对于 $n=4\times 10^5$ 约 6 个单词，因此每次查询检查约 $16 \times 6 \approx 100$ 个候选，计算汉明距离时用 popcount 加速，可接受。

关键优化点

分块：利用 $k \le 15$ 的性质，若汉明距离 $\le 15$，则至少有一个 16 位的块完全相同（鸽巢原理），因此只需检查这些块对应的候选单词。

预计算：将每块 16 位转为整数，用 popcount 表加速汉明距离计算。

提前退出：在累加汉明距离时，若已超过 $k$ 则立即停止。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef unsigned short us;

const int N = 400010, M = 65536;
int n, m, k;
ull a1, a2;
bool s[N + 10][256], b[256], lst;
vector<int> vec[16][M]; // vec[block_id][value] = list of word indices
us num[N][16], pcnt[M], c[16];

// 生成字典的随机函数
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 = 1; i <= n; i++)
        for (int j = 0; j < 256; j++)
            s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}

int main() {
    // 读入
    cin >> n >> m >> a1 >> a2;
    gen(n, a1, a2);
    
    // 预处理：分块并建立索引
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 16; j++) {
            us val = 0;
            for (int k = 0; k < 16; k++)
                val += s[i][(j << 4) + k] << k;
            num[i][j] = val;
            vec[j][val].push_back(i);
        }
    }
    
    // 预处理 popcount 表
    for (int i = 1; i < M; i++) pcnt[i] = pcnt[i >> 1] + (i & 1);
    
    // 处理查询
    bool lastans = 0;
    while (m--) {
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        
        // 读入 16 进制串并转为二进制
        for (int j = 0; j < 64; j++) {
            char ch; cin >> ch;
            int x = (ch >= '0' && ch <= '9') ? ch - '0' : ch - 'A' + 10;
            for (int l = 0; l < 4; l++)
                b[(j << 2) + l] = (x >> (3 - l)) & 1;
        }
        
        cin >> k;
        
        // 异或解密
        if (lastans)
            for (int j = 0; j < 256; j++) b[j] ^= 1;
        
        // 计算当前串的块值
        for (int j = 0; j < 16; j++)
            for (int l = 0; l < 16; l++)
                c[j] += b[j * 16 + l] << l;
        
        // 查询
        bool ans = 0;
        for (int j = 0; j < 16 && !ans; j++) {
            for (int t : vec[j][c[j]]) {
                int tot = 0;
                for (int l = 0; l < 16; l++) {
                    tot += pcnt[num[t][l] ^ c[l]];
                    if (tot > k) break;
                }
                if (tot <= k) {
                    ans = 1;
                    break;
                }
            }
        }
        
        cout << ans << '\n';
        lastans = ans;
    }
    return 0;
}