CF1017D The Wu

Childan 正在编造一个传奇故事，并试图将他伪造的——具有强烈“Wu”感的项链——卖给 Kasoura 夫妇。但 Kasoura 先生对 Childan 的故事提出了质疑，因此他打算就 Childan 所谓的“私人珍宝”项链提出几个问题。 这个“私人珍宝”是一个包含 $m$ 个“01 串”的多重集 $S$。 “01 串”是指长度为 $n$，仅由字符“0”和“1”组成的字符串。例如，当 $n=4$ 时，字符串“0110”、“0000”和“1110”都是“01 串”，但“00110”（有 $5$ 个字符，不是 $4$ 个）和“zero”（包含不允许的字符）都不是。 注意，多重集 $S$ 可以包含相同的元素。 Kasoura 先生会多次给出一个“01 串” $t$，并询问 Childan：在多重集 $S$ 中，有多少个字符串 $s$ 使得二者的“Wu”值不超过 $k$。 Kasoura 夫妇认为，如果 $s_i = t_i$（$1\leq i\leq n$），那么该字符对的“Wu”值为 $w_i$，否则为 $0$。两个“01 串”的“Wu”值为每一位字符对的“Wu”值之和。注意，每个“01 串”的长度均为 $n$。 例如，若 $w=[4, 5, 3, 6]$，“1001”与“1100”的“Wu”值为 $7$，因为这两个字符串只有第 1 位和第 3 位字符相同，所以 $w_1+w_3=4+3=7$。 你需要帮助 Childan 回答 Kasoura 先生的所有询问。即，对于每个询问，找出多重集 $S$ 中有多少个字符串与给定的 $t$ 的“Wu”值不超过 $k$。

第一行包含三个整数 $n$、$m$ 和 $q$（$1\leq n\leq 12$，$1\leq m, q\leq 5 \times 10^5$）——“01 串”的长度、多重集 $S$ 的大小以及询问的数量。 第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$0 \le w_i \le 100$）——第 $i$ 位字符的权值。 接下来的 $m$ 行，每行一个长度为 $n$ 的“01 串” $s$，表示多重集 $S$ 中的一个字符串。 接下来的 $q$ 行，每行包含一个长度为 $n$ 的“01 串” $t$ 和一个整数 $k$（$0\leq k\leq 100$），表示一个询问。

对于每个询问，输出该询问的答案。

在第一个样例中，可以得到： ("01", "00") 的 "Wu" 值为 $40$。 ("10", "00") 的 "Wu" 值为 $20$。 ("11", "00") 的 "Wu" 值为 $0$。 ("01", "11") 的 "Wu" 值为 $20$。 ("10", "11") 的 "Wu" 值为 $40$。 ("11", "11") 的 "Wu" 值为 $60$。 在第一个询问中，("11", "00") 和 ("10", "00") 满足条件，因为它们的 "Wu" 值不超过 $20$。 在第二个询问中，所有字符串都满足条件。 在第三个询问中，("01", "11") 和 ("01", "11") 满足条件。注意，由于多重集中有两个“01”，答案为 $2$，而不是 $1$。 在第四个询问中，随着 $k$ 的增大，("10", "11") 也满足条件。 在第五个询问中，随着 $k$ 的增大，("11", "11") 也满足条件。 由 ChatGPT 4.1 翻译