2024牛客寒假算法基础集训营2-c Tokitsukaze and Min-Max XOR

来源

题目

Tokitsukaze 有一个长度为 n 的序列 a1,a2,…,an和一个整数 k。

她想知道有多少种序列 b1,b2,…,bm满足：
 

其中 ⊕\oplus⊕ 为按位异或，具体参见 百度百科：异或 

答案可能很大，请输出  mod1e9+7 后的结果。

输入描述:

第一行包含一个整数 T(1≤T≤2e5)，表示 T 组测试数据。对于每组测试数据：第一行包含两个整数 n, k (1≤n≤2⋅e5; 0≤k≤1e9)。第二行包含 nnn 个整数 a1,a2,…,an (0≤ai≤1e9)。

输出描述:

对于每组测试数据，输出一个整数，表示答案   mod1e9+7  后的结果。

输入

3
3 2
1 3 2
5 3
1 3 5 2 4
5 0
0 0 0 0 0

输出

6
10
31

思路

       容易知道 b1,…,bm 实际上是 a 的一个子序列，并且由于我们只关注子序列中的最大值和最小值，因此可以先对 a 从小到大排序，再选择子序列。接着对子序列中的最大值进行分类，可以分成 n 类。即从左到右依次枚举 ai 作为子序列中的最大值，那么最小值就会在 aj, j∈[0,i] 中选。当满足 ai⊕aj≤k，那么以 ai 为最大值，aj 为最小值的子序列的数量就是 2的max{0,i−j−1}次方，特别的当 i=j 时答案为 1。

       暴力的做法就是逐个枚举 aj 判断是否满足条件，时间复杂度是 O() 的。由于涉及到异或运算所以尝试能不能用 trie 来维护 aj 的信息。如果 aj 满足条件，那么对答案的贡献是 ，也就是 ，因此在把 aj 按位插入 trie 中时，同时在对应节点加上。

       枚举到 ai 时，此时已经往 trie 中插入了 a0∼ai−1，枚举 ai 的每一位，用 xi 和 ki 分别表示 ai 和 k 在二进制下第 i 位上的值，s表示累加和。

        1.当xi=1，ki=1时，显然另一数aj这一位是1的情况都是可以的，因为 1⊕1=0<1，所以s加上这一位为1的节点的值了，下一步走0节点。

        2.当xi=0，ki=1时，同理s加上0节点的值，下一步走1节点.

        3.当xi=1，ki=0时，0节点必然不成立，因为 1⊕0=1>0，下一步走1节点。

        4.当xi=0，ki=0时，同理，1节点必然不成立，下一步走0节点。

最后以 ai 为最大值的子序列的数量就是。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define double long double
typedef long long ll;
const int N = 2e5+100;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f3f3f3f;
//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int a[N];
int to[N * 35][2];
int val[N * 35];
int tot = 0;void insert(int x,int c) {int p = 0;for (int i = 30; i >= 0; i--) {int v = (x >> i & 1);if (!to[p][v]) {to[p][v] = ++tot;}val[to[p][v]] = (val[to[p][v]] + c) % mod;p = to[p][v];}
}int sum(int x,int k) {int p = 0, res = 0;for (int i = 30; i >= 0; i--) {int vx = (x >> i & 1), vk = (k >> i & 1);if (vk == 1 && vx == 1) {res = (res + val[to[p][1]]) % mod;p = to[p][0];} else if (vk == 1 && vx == 0) {res = (res + val[to[p][0]]) % mod;p = to[p][1];} else {p = to[p][vx];}if (!p) break;if (!i) res = (res + val[p]) % mod;}return res;
}int ksm(int x,int n) {int res = 1;while (n) {if (n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;
}void solve() {int n,k;cin >> n >> k;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);tot = 0;for (int i = 0; i <= n * 32; i++) {val[i] = 0;to[i][0] = to[i][1] = 0;}int ans = 0;for (int i = 1; i <= n; i++) {ans = (ans + 1 + ksm(2,i - 1) * sum(a[i - 1],k) % mod) % mod;insert(a[i - 1],ksm(ksm(2,i),mod - 2));}cout << ans << '\n';
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--)solve();return 0;
}