Atcoder Regular Contest 139 F. Many Xor Optimization Problems | Alpha1022's Blog

[Alpha1022]

https://www.alpha1022.me/articles/arc139f.htm

参考自 wlzhouzhuan。 考虑枚举序列的标准基底。设秩为 (k)，其中元素的最高位分别为 (a_0 < a_1 < \dots < a_{k-1})。 于是，贡献由三部分组成：秩为 (k) 的序列个数、标准基底个数，以及最大异或和的期望值。 秩为 (k) 的序列个数是经典问题，在此处已经讨论过（不过这里先不考虑基是哪些元素），于是直接给出结论： [ 2^