2025牛客多校第五场 K.完美旅程 J.最快覆盖问题 E.神秘异或操作 个人题解

E.Mysterious XOR Operation

位运算

思路

观察两个数\(a,b\)，研究二者神秘异或后第\(pos\)位对答案的贡献：
设\(pos\)位上二者的\(bit\)不同，记二者\(0\sim pos-1\)位上\(1\)的个数为\(cnt_{a},cnt_{b}\)

• 则\(a\wedge b\)在\(0\sim pos\)位上的\(1\)个数为\(cnt_{a}-k+cnt_{b}-k\)，其中\(k\)为\(a,b\)在\(0\sim pos\)位上同时为\(1\)的个数
  
• 则\(a\wedge b\)在\(0\sim pos\)位上的\(1\)个数与\(cnt_{a}+cnt_{b}\)的奇偶性直接挂钩
  

创建三维数组\(cnt[28][2][2]\)，其中\(cnt[pos][bit][1/0]\)表示当前遍历到第\(pos\)位，当前位为\(bit\)，\(0\sim pos-1\)位上\(1\)的个数\(\&1\)后为\(1/0\)的个数
每次插入一个新的数，都更新\(cnt[pos][bit][1/0]\)，让贡献加上\(cnt\)乘以当前\(pos\)的十进制数即可
代码实现

[code]#include#include#include#include#include#include#include#includeusing namespace std;using ll = long long;#define rep(i, a, b) for(ll i = (a); i = (b); i --)//#define see(stl) for(auto&ele:stl)coutpos)&1;            ans+=1ll*(1