P6990 [NEERC 2014] Filter

你正在开发一个新的高性能数据库引擎——即时压缩和处理编解码器（Instant Compression and Processing Codec，ICPC）。ICPC 存储用户活动记录。每条用户活动记录都有一个整数用户标识符。记录存储在多个数据文件中。每个数据文件都是压缩的，可以包含来自多个用户的记录，然而 ICPC 必须处理查询以查找特定的用户子集。为此，必须有一种方法可以快速确定哪些数据文件可能包含特定用户的记录，然后再尝试解压它们，因为这可能是一个耗时且消耗 CPU 的过程。 ICPC 使用一种称为布隆过滤器的算法。ICPC 中的实现方式如下所述。对于每个 ICPC 数据库，选择以下整数参数： $m$ 是过滤器中的位数； $f$ 是过滤器中的哈希函数数量； $a_{i}$ 是哈希函数的参数，$0 \le i$。 为每个数据文件计算布隆过滤器的值。数据文件的布隆过滤器是一个 $m$ 位的向量。只有当在该数据文件中存在某个用户标识符 $u_{k}$ 的记录时，位号 $j (0 \le j < m)$ 才会被设置为 1，并且对于某个哈希函数 $i (0 \le i < f)$，满足以下等式： $$j = (u_{k} \cdot a_{i}) \mod m$$ (1) 你的任务是实现 ICPC 过滤逻辑。给定过滤器参数和若干数据文件的值以及一组用户标识符。你的任务是确定哪些数据文件可能包含指定集合中至少一个用户标识符的记录。只有当对于所有 $i (0 \le i < f)$，其过滤器值中由等式 (1) 给出的所有位 $j$ 都被设置为 1 时，数据文件才可能包含用户标识符 $u_{k}$ 的记录。

输入文件的第一行包含过滤器参数——整数 $m, f$ 和 $a_{i}$，其中 $0 \le i < f (1 \le m \le 1000, 1 \le f \le 100, 1 \le a_{i} < 2^{31})$。 输入文件的第二行包含一个整数 $n$——数据文件的数量 $(1 \le n \le 1000)$。接下来的 $n$ 行中的每一行包含相应文件的布隆过滤器值，以十六进制形式表示。每个值由一个 $\lceil m/4 \rceil$ 个十六进制数字的字符串表示（取值为 $0123456789abcdef$ 中的一个）。字符串的第一个数字表示值的位 $0-3$（按从十六进制数字的最低有效位到最高有效位的顺序存储），第二个数字表示位 $4-7$，第三个表示 $8-11$，等等。当 $m \mod 4 eq 0$ 时，最后一个十六进制数字表示值的最后 $m \mod 4$ 位，以其最低有效位表示。 输入文件的下一行包含一个整数 $q$——查询中的用户标识符数量 $(1 \le q \le 1000)$，后跟 $q$ 个整数 $u_{k}$——查询中的一组不同的用户标识符 $(1 \le u_{k} < 2^{31})$。

在输出文件中写入一行，包含整数 $s$——可能包含指定集合中至少一个用户标识符的记录的数据文件数量，后跟 $s$ 个数字 $d_{t} (0 \le d_{t} < n)$——对应数据文件的从 0 开始的编号，按升序排列。

时间限制：1 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。