配点: 6 点
問題文
N 个非负整数 A_1,A_2,\ldots,A_N 。
0 以上 2^D 的整数 x , 选择最大化i=1,2,\ldots,N 请找出有多少个满足以下条件的情况。
- A_i 和 按字典顺序比较 x 的按位与(按位逻辑与)\operatorname{AND})不是 0 。
关于按位与(按位逻辑与\operatorname{AND})
非負整数 A,B 的按位与(按位逻辑与)\operatorname{AND})、A\ \operatorname{AND}\ B 定义如下。
- A\ \operatorname{AND}\ B 以二进制表示法 2^k\ (k\geq0) 中的位数为A,B 以二进制表示法 2^k 的两位数字 如果 1 如果 1,否则 输出为 0 。
制約
- 1\leq N\leq20
- 0\leq D\leq60
- 0\leq A_i<2^D\ (1\leq i\leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N D A_1 A_2 \cdots A_N
出力
N 满足所有条件的整数 x 的编号。
入力例 1
4 3 1 3 4 5
出力例 1
2
0 以上 2^3 的整数 x 分别满足以下条件。
- 0 不满足任何条件。
- 1 是 您也可以写 1,2,4 满足第一个条件,但3 不满足第二个条件。
- 2 是 您也可以写 2 满足第一个条件,但1,3,4 不满足第二个条件。
- 3 是 您也可以写 1,2,4 满足第一个条件,但3 不满足第二个条件。
- 4 是 您也可以写 3,4 满足第一个条件,但1,2 不满足第二个条件。
- 5 满足所有条件。
- 6 是 您也可以写 2,3,4 满足第一个条件,但1 不满足第二个条件。
- 7 满足所有条件。
因此,答案是 2 。
入力例 2
5 21 1050624 32772 493952 144 869120
出力例 2
869120
入力例 3
20 60 216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760
出力例 3
977902973481140224
输入或输出的值 32 可能无法容纳在位整数中。