#D0501. 掩码

掩码

题目描述

33DAI 有两组无符号整数。

第一组有 nn 个数 a1ana_1\sim a_n。第二组有 mm 个数 b1bmb_1\sim b_m

我们要在第二组里找这样的数:用这个数和第一组里的每个数做按位与运算,算出来的结果还都是第一组里的那个数。现在问第二组里有几个这样的数呢?

形式化的说,求有多少个 bi(1im)b_i(1\le i\le m),满足“对于任意的 1m1\sim m 之内的 jj,有 bi&aj=ajb_i\&a_j=a_j

什么是按位与运算:即两个数在二进制下每一位都进行与运算组合出来的结果,比如 (1010)2&(1100)2=(1000)2(1010)_2 \& (1100)_2 = (1000)_2,在 C++ 中,可以用 a & b 来计算 aabb 按位与运算的结果。

输入格式

第一行两个数 n,mn,m

第二行 nn 个数:a1ana_1\sim a_n

第三行 mm 个数:b1bmb_1\sim b_m

输出格式

一个整数,即第二组里有几个这样的数。

3 7
1 4 5
1 2 3 4 5 6 7 
2

样例 1 解释

只有 5,75,7 满足要求,所以输出 22

3 4
3 3 3
7 7 7 7
4

样例 2 解释

可能有重复的数。

数据规模与约定

对于 100%100\% 的数据,1n,m1051 \le n,m \le 10^50ai,bi<2300\le a_i,b_i\lt 2^{30}

  • 子任务 1(30 分):保证 0ai,bi10\le a_i,b_i\le 1
  • 子任务 2(30 分):保证 n,m1000n,m\le 1000
  • 子任务 3(40 分):没有特殊限制。