#P6818. [2019年广州]异或

    ID: 6650 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划线性 DP计数 DP数据结构异或 TrieCF2200

[2019年广州]异或

异或

题目描述

给定一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n,以及限制 LL。

称一个序列 b1,b2,…,bkb_1,b_2,\ldots,b_k 是好的,当且仅当对任意 1≤i<j≤k1\le i<j\le k,均满足

bi⊕bj≥L,b_i\oplus b_j\ge L,

其中 ⊕\oplus 表示按位异或。

求原序列中好的非空子序列的数量。子序列由下标 1≤i1<i2<⋯<ik≤n1\le i_1<i_2<\cdots<i_k\le n 选出;不同下标选择分别计数。单个元素组成的子序列也满足条件。

答案对 109+710^9+7 取模。

输入格式

第一行两个整数 n,Ln,L。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一行一个整数,表示好的非空子序列数量对 109+710^9+7 取模的结果。

样例 1 输入

3 2
0 1 2

样例 1 输出

5

样例 1 解释

三个单元素子序列均合法;两个元素组成的合法子序列为 (0,2)(0,2)、(1,2)(1,2),共 55 个。

补充样例 2 输入

3 0
7 7 7
7

任意非空下标集合都合法,共 23−1=72^3-1=7 个。

补充样例 3 输入

3 1
7 7 7
3

两个相同值的异或为 0<10<1,因此只有三个单元素子序列合法。

数据范围与子任务

所有数据满足 1≤n≤1051\le n\le10^5,0≤ai,L<2600\le a_i,L<2^{60}。

子任务 分值 附加限制
1 2020 n≤20n\le20
2 2525 n≤200n\le200
3 n≤2000n\le2000
4 3030 无