QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#642022#7411. Bitwise Xor11d10xyWA 0ms5876kbC++141.2kb2024-10-15 08:59:372024-10-15 08:59:38

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 08:59:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5876kb
  • [2024-10-15 08:59:37]
  • 提交

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'