题目链接:HDU5269
【分析】容易得到两个数a,b异或后lowbit的值就是当a,b的最低p-1位相同,lowbit值为2^p;比赛的时候想从左往右把每一位上出现过的0的次数和1的次数用sum[29][2]记下来,然后处理到a[i]时,a[i]和a[1~i-1]的所有lowbit之和为它的每一位值p:f[i]*sum[i][p^1]之和;可是这样一个数可能会被计算多次,怎样让每个数只计算一次且是最低位的那次;比赛中就一直卡住了;其实可以用字典树低位到高位插入,每次都插29位,插入的时候累加每个f[i]*sum[ch[i][p^1]]即可。
【AC CODE】93ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 50000+10, MOD = 998244353; int ch[35*MAXN][2], sum[35*MAXN], cnt, ans; int newnode() { ch[cnt][0] = ch[cnt][1] = -1; sum[cnt++] = 0; return cnt-1; } void insert(int u, int v) { rep(i,0,29) { int p = (bool)(v&(1<<i)); if(~ch[u][p^1]) ans = (ans+(LL)(1<<(i+1))*sum[ch[u][p^1]]%MOD)%MOD; if(-1 == ch[u][p]) ch[u][p] = newnode(); sum[u]++; u = ch[u][p]; } } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int t,count = 0; scanf("%d%*c", &t); while(t--) { int n; scanf("%d%*c", &n); cnt = ans = 0; int root = newnode(); rep(i,0,n) { int a; scanf("%d", &a); insert(root,a); } printf("Case #%d: %d\n", ++count,ans); } return 0; }