本文主要是介绍hdu 5269 ZYB loves Xor I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
ZYB喜欢研究Xor，现在他得到了一个长度为n的数组A。于是他想知道：对于所有数对(i,j)(i∈[1,n],j∈[1,n])，lowbit(AixorAj)之和为多少.由于答案可能过大，你需要输出答案对998244353取模后的值 定义lowbit(x)=2k，其中k是最小的满足(x and 2k)>0的数 特别地：lowbit(0)=0
输入：
一共T(T≤10)组数据，对于每组数据： 第一行一个正整数n，表示数组长度 第二行n个非负整数，第i个整数为Ai n∈[1,5∗104]，Ai∈[0,229]输出：
每组数据输出一行Case #x: ans。x表示组数编号，从1开始。ans为所求值。
官方题解：
我们考虑，当A xor B的答案为2p时，A和B表示成二进制数后末p−1位肯定相同 于是我们维护一颗字母树，将每个数表示成二进制数后翻转可以下，插入字母树 统计答案时，我们找出Ai的二进制数翻转后在字母树上的路径，对于路径上每个点x，设他走的边是v，且当前为第k位，则和他xor后lowbit为2k的数的个数为trans(x,v^1)的子树大小。 trans(x,v)表示字母树上在结点x，走连出去的字母为v的边到达的结点 时间复杂度：O(nlogA)
分析：
刚开始用map瞎搞，TLE~，怎么都没想到用字典树啊，还是智商不够用。
以下附上代码：
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>using namespace std;typedef long long ll;
typedef unsigned long long ull;const int maxn = 50005;
const int mod = 998244353;struct Node{int cnt;Node *l, *r;//0 1~Node(){}
};struct Tree{Node *root;Tree(){root = new Node;root->l = 0; root->r = 0;}void insert(int v){Node *p = root;for(int i = 0; i < 30; i++){if(v&(1<<i)){//1 if(p->r == 0){Node *q = new Node;q->cnt = 0;q->l = 0;q->r = 0;p->r = q;}p = p->r;p->cnt++;}else{//0if(p->l == 0){Node *q = new Node;q->cnt = 0;q->l = 0;q->r = 0;p->l = q;}p = p->l;p->cnt++;}}}int find(int v){Node *p = root;int res = 0;for(int i = 0; i < 30; i++){if(v&(1<<i)){//1if(p->l != 0){res += (p->l->cnt)*(1<<i);res %= mod;}p = p->r;}else{//0if(p->r != 0){res += (p->r->cnt)*(1<<i);res %= mod; }p = p->l;}}return res;}~Tree(){ }};int n;
int a[maxn];int main()
{int t;int ans;scanf("%d",&t);for(int k = 1; k <= t; k++){Tree x;scanf("%d",&n);ans = 0;for(int i = 0; i < n; i++){scanf("%d",&a[i]);x.insert(a[i]);}for(int i = 0; i < n; i++){ans += x.find(a[i]);ans %= mod;}printf("Case #%d: %d\n",k,ans);}return 0;
}
这篇关于hdu 5269 ZYB loves Xor I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
