#P9626. O(rand)

    ID: 6244 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高容斥原理全子集枚举Pascal 递推增量维护稀疏状态重置同余的加减乘运算二项式反演

O(rand)

题目描述

给出一个长度为 nn 的非负整数序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,这个数列元素互不相等。从中选出 1∼k1\sim k 个数字,使它们按位与结果为 SS,按位或结果为 TT。求可选择的方案数。

输入格式

第一行四个整数 n,k,S,Tn,k,S,T。

第二行 nn 个非负整数,表示 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。

输出格式

输出一个整数,表示方案数。

样例

3 3 0 3
1 2 3
2

我们可以选择集合 {1,2}\{1,2\},{1,2,3}\{1,2,3\}。

5 3 1 7
3 4 9 1 5
2
5 4 0 15
3 4 9 1 5
3

数据范围

1≤k≤n≤501\le k \le n \le 50,0≤ai,S,T<2180 \le a_i,S,T < 2^{18}。