Link to topic
Atcoder direction
Luogu direction
Problem solution
Considering the nature of XOR, a number being XORed an even number of times is equivalent to
0
0
0, a number is exclusive or an odd number of times is equivalent to only one exclusive or
Consider each number if it appears
b
1
,
b
2
,
.
.
.
,
b
no
b_1,b_2,…,b_n
b1?,b2?,…,bn? times, where
b
1
+
b
2
+
.
.
.
+
b
no
=
k
b_1 + b_2 + … + b_n=k
b1? + b2? + … + bn?=k
Then the number of times this happens is
(
no
b
1
)
?
(
no
?
b
1
b
2
)
?
.
.
.
?
(
no
?
b
1
?
b
2
?
.
.
.
?
b
no
?
1
b
no
)
(^{b_1}_{n})*(^{b_2}_{n-b_1})*…*(^{b_n}_{n-b_1-b_2-…-b_{n-1 }})
(nb1)?(n?b1?b2)?…?(n?b1b2…?bn?1?bn)
If the number of times needs to be even, then according to
l
u
c
a
the s
lucas
lucas theorem,
a
1
,
a
2
,
.
.
.
,
a
no
a_1,a_2,…,a_n
a1?,a2?,…,an? must all be
k
k
subset of k binary representations
This transforms the problem into for each
k
k
The binary digits of k can be filled in
a
1
,
a
2
,
.
.
,
a
no
a_1,a_2,..,a_n
a1?,a2?,..,an?, find the XOR sum of the sum of the numbers of each scheme
Consider digits
d
p
dp
dp, order
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] means to the first
i
i
When i bit, the previous carry + the currently added
a
i
a_i
ai? for
j
j
number of solutions for j
-
k
k
k’s
i
i
i bit is 0,
d
p
[
i
]
[
j
/
2
]
?
>
d
p
[
i
?
1
]
[
j
]
dp[i][j/2] \;->\;dp[i-1][j]
dp[i][j/2]?>dp[i?1][j]
-
k
k
k’s
i
i
i bit is 1,
d
p
[
i
?
1
]
[
j
]
?
>
d
p
[
i
]
[
j
/
2
+
a
i
]
dp[i-1][j]\;->\;dp[i][j/2 + a_i]
dp[i?1][j]?>dp[i][j/2 + ai?]
When counting the answers at the end, the product of the total number of solutions and the number of current solutions must be an odd number, and
j
j
j is an odd number, the answer can be XORed
2
i
2^i
2i
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N(1100);
int n,k,ans,a[N];
bool dp[55][N<<1];
inline int read(){<!-- -->
int FF=0,RR=1;
char ch = getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1) + (FF<<3) + ch-48;
return FF*RR;
}
void calc(int p){<!-- -->
int ways=1;
for(int i=p + 1;i<=51;i + + ) if(k>>(i-1) & amp;1) ways=ways*n%2;
if(!ways) return;
for(int i=1;i<N<<1;i + =2) if(dp[p][i]) ans^=1ll<<(p-1);
}
signed main(){<!-- -->
n=read(),k=read();
for(int i=1;i<=n;i + + ) a[i]=read();
dp[0][0]=1;
for(int i=1;i<=51;i + + ){<!-- -->
if(k>>(i-1) & amp;1) for(int j=0;j<N<<1;j + + ) for(int l=1;l<=n;l + + ) dp [i][j/2 + a[l]]^=dp[i-1][j];
else for(int j=0;j<N<<1;j + + ) dp[i][j/2]^=dp[i-1][j];
calc(i);
// cout<<ans<<'\\
';
}
printf("%lld",ans);
return 0;
}
//dp[i][j]: the value of %2 of the number of schemes where the sum of the i-th and the current bit is j