← 返回题目列表

AtCoder · tokiomarine2020_e

E. O(兰特)

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给出的是 N 两两不同的非负整数 A_1,A_2,\ldots,A_N。计算从给定数字中选择包含 1 和 K 个数字的集合的方式数,使满足以下两个条件:

  • 所选数字的按位与为 S.
  • 所选数字的按位或为 T.

约束

  • 1 \leq N \leq 50
  • 1 \leq K \leq N
  • 0 \leq A_i < 2^{18}
  • 0 \leq S < 2^{18}
  • 0 \leq T < 2^{18}
  • A_i \neq A_j (1 \leq i < j \leq N)

输入

输入由标准输入按以下格式给出:

N K S T
A_1 A_2 ... A_N

输出

打印答案。


示例输入 1

3 3 0 3
1 2 3

示例输出 1

2

当我们选择时,条件得到满足 \{1,2\} or \{1,2,3\}.


示例输入 2

5 3 1 7
3 4 9 1 5

示例输出 2

2

示例输入 3

5 4 0 15
3 4 9 1 5

示例输出 3

3