QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401799 | #7411. Bitwise Xor | james1BadCreeper# | WA | 1ms | 7772kb | C++14 | 1.3kb | 2024-04-29 13:54:55 | 2024-04-29 13:54:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int P = 998244353;
const int N = 3e5 + 5;
int n;
i64 a[N], x;
int ch[N * 61][2], tot, sz[N * 61];
void insert(i64 val, int ad) {
int p = 1; sz[1] = (sz[1] + ad) % P;
for (int i = 59; i >= 0; --i) {
int c = val >> i & 1;
if (!ch[p][c]) ch[p][c] = ++tot;
p = ch[p][c]; sz[p] = (sz[p] + ad) % P;
}
}
int query(int p, int dep, i64 val) {
if (p == 0) return 0;
if (dep == 0) return sz[p];
int pv = val >> dep - 1 & 1, px = x >> dep - 1 & 1, ans = 0;
// 选择 0
if (pv > px) ans = (ans + sz[ch[p][0]]) % P;
else if (pv == px) ans = (ans + query(ch[p][0], dep - 1, val)) % P;
if ((pv ^ 1) > px) ans = (ans + sz[ch[p][1]]) % P;
else if ((pv ^ 1) == px) ans = (ans + query(ch[p][1], dep - 1, val)) % P;
return ans;
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> x; tot = 1;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
int val = (query(1, 60, a[i]) + 1) % P;
cout << val << "\n";
ans = (ans + val) % P;
insert(a[i], val);
}
cout << ans << "\n";
return 0;
}
// 相邻
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7772kb
input:
3 0 0 1 2
output:
1 2 4 7
result:
wrong answer 1st numbers differ - expected: '7', found: '1'