Problem: https://atcoder.jp/contests/arc156/tasks/arc156_d
My note:
Google drive: https://drive.google.com/file/d/1It475dOHDzrt0DCm0so95x4y7ocn51pT/view?usp=share_link
Tencent: https://docs.qq.com/pdf/DU3pOalBZbW9DbVV1
Code (C/C++ are both OK, please use gcc/g++ compilers):
Spoiler
#include <stdio.h>
#pragma GCC optimize("Ofast") // -Ofast 预编译优化
#define ll long long
ll a[1005];
ll dp[45][2400], pre[45][2400];
ll kbits[45], tot=0;
int main(void){
//freopen("test1.txt", "r", stdin);
ll n, k;
scanf("%lld %lld", &n, &k);
ll mxa = -1;
for(ll i = 1; i <= n; ++i){
scanf("%lld", a+i);
mxa = a[i] > mxa?a[i]:mxa;
}
for(ll bit = 0; bit <= 40; ++bit){ //k一共40位
if(k & (1ll << bit)){
++tot; //tot就是上述分析中的M!
kbits[tot] = bit;
}
}
dp[0][0] = 1;
for(ll s = 0; s <= 2*mxa; ++s){
pre[0][s] = 1;
}
for(ll bit = 1; bit <= tot; ++bit){
for(ll s = 0; s <= 2*mxa; ++s){
for(ll i = 1; i <= n; ++i){
if(s >= a[i]){
//要注意出界(>2*mxa)的情形
ll lb = (s-a[i])<<(kbits[bit]-kbits[bit-1]);
ll ub = lb + (1ll<<(kbits[bit]-kbits[bit-1])) - 1ll;
if(lb > 2*mxa) continue;
if(ub > 2*mxa) ub = 2*mxa;
//计算前缀和的时候, 要注意lb==0的情况, 不要搞出0-1==-1这种下标!
dp[bit][s] = dp[bit][s] ^ pre[bit-1][ub] ^ (lb?pre[bit-1][lb-1]:0);
}
}
}
for(ll s = 0; s <= 2*mxa; ++s){
pre[bit][s] = (s == 0?dp[bit][s]:(dp[bit][s]^pre[bit][s-1])); //前缀和优化
}
}
ll ans = 0;
if(n & 1){
for(ll bit = 1; bit < tot; ++bit){
for(ll s = 1; s <= 2*mxa; ++s){
ll curbit = kbits[bit];
for(ll j = 0; j < kbits[bit+1] - kbits[bit]; ++j){
//We only care the places between [kbits[bit], kbits[bit+1]). For the places >= kbits[bit+1], dp[bit+1][...] will handle them.
//我们只扫描[kbits[bit], kbits[bit+1])之间的位。对于>=kbits[bit+1]的位, 我们让dp[bit+1]帮我们处理。
if((s & (1ll << j)) && dp[bit][s]){
ans ^= (1ll << (j+curbit));
}
}//for j (bit of s)
}//for s
}//for bit
}
for(ll s = 1; s <= 2*mxa; ++s){
ll curbit = kbits[tot];
for(ll j = 0; j <= 25; ++j){
if((s & (1ll << j)) && dp[tot][s]){
ans ^= (1ll << (j+curbit));
}
}
}
printf("%lld\n", ans);
return 0;
}