题意：给一个序列[a, a + n)，求Σlowbit(ai, aj)，i,j∈[0,n)。
思路：lowbit与位有关，于是按位统计即可，如果lowbit=2^k，则前k位相同，前缀相同，于是想到用字典树来统计。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #pragma comment(linker, "/STACK:10240000,10240000")#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>#include <algorithm>#include <queue>using namespace std;const int maxn = 2e6;const int md = 998244353;struct Trie { int ch[maxn][2], val[maxn], sz; void init() { sz = 1; memset(ch, 0, sizeof(ch)); memset(val, 0, sizeof(val)); } void insert(int x) { int p = 0, cnt = 0; while (cnt < 31) { if (ch[p][x & 1]) p = ch[p][x & 1]; else p = ch[p][x & 1] = sz ++; val[p] ++; cnt ++; x >>= 1; } } int solve(int p, int dep) { int buf = (long long)val[ch[p][0]] * val[ch[p][1]] % md * ((long long)1 << dep) % md; if (ch[p][0]) buf = (buf + solve(ch[p][0], dep + 1)) % md; if (ch[p][1]) buf = (buf + solve(ch[p][1], dep + 1)) % md; return buf; }};Trie solver;int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int T, cas = 0, n; cin >> T; while (T --) { cin >> n; solver.init(); for (int i = 0; i < n; i ++) { int x; scanf("%d", &x); solver.insert(x); } printf("Case #%d: %d
", ++ cas, solver.solve(0, 1)); } return 0;} |