眉山做网站的公司,网站托管费,网站备案官网,WordPress考勤模板Problem - E - Codeforces
题意#xff1a; 思路#xff1a;
这其实是一个套路题
区间异或转化成前缀异或#xff0c;然后枚举 i
对于每一个 i#xff0c;ai ^ x k#xff0c;对 x 计数
先建一棵字典树#xff0c;然后在字典树上计数
先去对 k 的部分计数 思路
这其实是一个套路题
区间异或转化成前缀异或然后枚举 i
对于每一个 iai ^ x k对 x 计数
先建一棵字典树然后在字典树上计数
先去对 k 的部分计数再对 k 的部分计数
如果 k 的第 j 位是1那么沿着走就行否则对 (k j 1) ^ 1的部分计数然后继续沿着走
最后的res cnt[p]是对 k 的部分计数
Code
#include bits/stdc.husing i64 long long;constexpr int N 1e6 10;
constexpr int M 1e6 10;
constexpr int P 2600;
constexpr i64 Inf 1e18;
constexpr int mod 1e9 7;
constexpr double eps 1e-6;int n, k;
int tot 1;
int a[N], cnt[N * 30];
int tr[N * 30][2];void insert(int x) {int p 1;for (int j 30; j 0; j --) {int u (x j) 1;if (!tr[p][u]) tr[p][u] tot;p tr[p][u];cnt[p] ;}
}
i64 query(int x, int y) {int p 1;i64 res 0;for (int j 30; j 0; j --) {int u (x j) 1, v (y j) 1;if (v) {p tr[p][u ^ 1];}else {res cnt[tr[p][u ^ 1]];p tr[p][u];}}res cnt[p];return res;
}
void solve() {std::cin n k;for (int i 1; i n; i ) std::cin a[i];for (int i 1; i n; i ) a[i] ^ a[i - 1];i64 ans 0;for (int i 1; i n; i ) {insert(a[i - 1]);ans query(a[i], k);}std::cout ans \n;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;while (t--) {solve();}return 0;
}
