QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642022 | #7411. Bitwise Xor | 11d10xy | WA | 0ms | 5876kb | C++14 | 1.2kb | 2024-10-15 08:59:37 | 2024-10-15 08:59:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
constexpr i64 mod=998244353;
int n;i64 X;
namespace ds{
constexpr int N=300010*64;
int ch[N][2],sz[N],rt,tot;
void insert(int&u,int h,i64 x){
if(!u)u=++tot;
sz[u]++;
if(h==-1)return;
insert(ch[u][x>>h&1],h-1,x);
}
int dfs(int u,int h,i64 x){
if(h==-1)return sz[u];
int o=x>>h&1;
if(X>>h&1)return dfs(ch[u][o^1],h-1,x);
else return dfs(ch[u][o],h-1,x)+sz[ch[u][o^1]];
}
void clear(){
for(;tot;tot--){
sz[tot]=ch[tot][0]=ch[tot][1]=0;
}rt=0;
}
}
int main(){
scanf("%d%lld",&n,&X);
if(!X){
i64 ans=1;for(;n--;(ans*=2)%=mod);
printf("%lld",ans-1);
return 0;
}
int H=__lg(X);
map<i64,array<vector<i64>,2>>mp;
for(int i=1;i<=n;i++){
i64 x;scanf("%lld",&x);
mp[x&~((1<<H+1)-1)][x>>H&1].push_back(x&(1<<H)-1);
}
i64 ans=1;
for(auto X:mp){
ds::clear();
for(i64 x:X.second[1])ds::insert(ds::rt,H-1,x);
i64 s=1+X.second[0].size()+X.second[1].size();
for(i64 x:X.second[0])s+=ds::dfs(ds::rt,H-1,x);
(ans*=s)%=mod;
}
printf("%lld",(ans+mod-1)%mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
input:
3 0 0 1 2
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 2 0 1 2
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
3 3 0 1 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
7 4 11 5 5 8 3 1 3
output:
35
result:
ok 1 number(s): "35"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
10 0 1 1 0 0 1 0 0 0 1 1
output:
1023
result:
ok 1 number(s): "1023"
Test #6:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
10 0 1 1 0 1 0 1 1 0 1 0
output:
1023
result:
ok 1 number(s): "1023"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10 1 1 0 0 1 0 0 0 0 0 0
output:
26
result:
ok 1 number(s): "26"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
10 0 0 0 1 1 0 1 1 1 1 1
output:
1023
result:
ok 1 number(s): "1023"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10 1 0 0 0 0 0 1 1 0 0 1
output:
31
result:
ok 1 number(s): "31"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
10 2 3 3 3 0 3 1 2 2 1 2
output:
31
result:
ok 1 number(s): "31"
Test #11:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
10 0 2 1 1 1 1 2 0 1 2 0
output:
1023
result:
ok 1 number(s): "1023"
Test #12:
score: 0
Accepted
time: 0ms
memory: 5876kb
input:
10 1 2 2 2 3 2 3 3 1 2 3
output:
59
result:
ok 1 number(s): "59"
Test #13:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
10 0 0 0 0 1 1 1 0 2 3 2
output:
1023
result:
ok 1 number(s): "1023"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
10 3 0 2 2 2 1 2 3 0 2 1
output:
22
result:
ok 1 number(s): "22"
Test #15:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
10 232612786 899206785 627708234 142071418 602920154 868777585 1041571266 892732172 868993257 746093759 987356899
output:
109
result:
ok 1 number(s): "109"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
10 0 693036642 1030693062 419968059 741209191 591827389 259645735 276712455 734217910 177798129 94619093
output:
1023
result:
ok 1 number(s): "1023"
Test #17:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
10 635603548 611293890 811243506 517958533 561419149 895889603 689314144 76814806 428189482 659398653 905893003
output:
28
result:
ok 1 number(s): "28"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
10 598501421 901133473 1042356871 455409245 112433974 817368410 222953949 336845301 1006948209 370826440 272138888
output:
32
result:
ok 1 number(s): "32"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
10 569445936 869711746 277315301 943789204 430971232 323814634 798129975 683685773 693506183 425568840 820399918
output:
30
result:
ok 1 number(s): "30"
Test #20:
score: -100
Wrong Answer
time: 0ms
memory: 3720kb
input:
10 420556732312880218 1106881251557229935 479315094315300787 1150808909500812292 323682577963266475 778601139147884850 223606994709920530 180162865619996357 598163543343955050 759543442386927924 1066745884923649787
output:
1023
result:
wrong answer 1st numbers differ - expected: '76', found: '1023'