异或
题目描述
给定一个长度为 n 的序列 a1,a2,…,an,以及限制 L。
称一个序列 b1,b2,…,bk 是好的,当且仅当对任意 1≤i<j≤k,均满足
bi⊕bj≥L,
其中 ⊕ 表示按位异或。
求原序列中好的非空子序列的数量。子序列由下标 1≤i1<i2<⋯<ik≤n 选出;不同下标选择分别计数。单个元素组成的子序列也满足条件。
答案对 109+7 取模。
输入格式
第一行两个整数 n,L。
第二行 n 个整数 a1,a2,…,an。
输出格式
输出一行一个整数,表示好的非空子序列数量对 109+7 取模的结果。
样例 1 输入
3 2
0 1 2
样例 1 输出
5
样例 1 解释
三个单元素子序列均合法;两个元素组成的合法子序列为 (0,2)、(1,2),共 5 个。
补充样例 2 输入
3 0
7 7 7
7
任意非空下标集合都合法,共 23−1=7 个。
补充样例 3 输入
3 1
7 7 7
3
两个相同值的异或为 0<1,因此只有三个单元素子序列合法。
数据范围与子任务
所有数据满足 1≤n≤105,0≤ai,L<260。
| 子任务 |
分值 |
附加限制 |
| 1 |
20 |
n≤20 |
| 2 |
25 |
n≤200 |
| 3 |
n≤2000 |
| 4 |
30 |
无 |