#CF467B. Fedor 和新游戏

Fedor 和新游戏

CF467B Fedor and New Game

题目描述

\hspace{15pt}在你帮 George 和 Alex 搬进宿舍之后,他们去帮他们的朋友 Fedor 玩一款新的电脑游戏《Call of Soldiers 3》。

\hspace{15pt}游戏总共有 m+1m+1 个玩家,以及 nn 种士兵类型。玩家编号为 11 到 m+1m+1,士兵类型编号为 00 到 n−1n-1。每个玩家都有一支军队,第 ii 个玩家的军队可以用一个非负整数 xix_i 描述:若 xix_i 的二进制表示中第 jj 位为 11,则第 ii 个玩家的军队中拥有编号为 jj 的士兵类型。

\hspace{15pt}Fedor 是第 m+1m+1 个玩家。他认为,如果两名玩家的军队至多有 kk 种士兵类型不同(也就是说,两个数的二进制表示至多有 kk 位不同),那么这两名玩家就可以成为朋友。请你帮助 Fedor 计算有多少名玩家可以成为他的朋友。

输入格式

\hspace{15pt}第一行输入三个整数 $n,m,k \left(1 \leqq k \leqq n \leqq 20;\ 1 \leqq m \leqq 1000\right)$ 代表士兵类型数量、除 Fedor 外的玩家数量,以及成为朋友所允许的不同士兵类型数量的上限。

\hspace{15pt}此后 m+1m+1 行,第 ii 行输入一个整数 xi(0≦xi≦2n−1)x_i \left(0 \leqq x_i \leqq 2^n-1\right) 代表第 ii 个玩家的军队。最后一行为 Fedor 的军队。

输出格式

\hspace{15pt}在一行上输出一个整数,代表可以成为 Fedor 朋友的玩家人数。

测试样例

7 3 1
8
5
111
17

0

样例 1 解释

\hspace{15pt}Fedor 的军队为 x4=17x_4=17,其二进制表示为 (10001)2(10001)_2。其余三名玩家的军队分别为 8=(1000)28=(1000)_2、5=(101)25=(101)_2、111=(1101111)2111=(1101111)_2,它们与 1717 的二进制表示分别有 3,2,63,2,6 位不同,都超过了 k=1k=1,因此没有玩家可以成为 Fedor 的朋友,答案为 00。

3 3 3
1
2
3
4

3

样例 2 解释

\hspace{15pt}Fedor 的军队为 x4=4x_4=4,其二进制表示为 (100)2(100)_2。其余三名玩家的军队分别为 1=(001)21=(001)_2、2=(010)22=(010)_2、3=(011)23=(011)_2,它们与 44 的二进制表示分别有 2,2,32,2,3 位不同,都不超过 k=3k=3,因此三名玩家都可以成为 Fedor 的朋友,答案为 33。