Description：

有 $n$ 个数 $A_1,A_2,\dots,A_n$ ，在其中选出恰好 $k$ 个数 $B_1,B_2,\dots,B_k$ ，满足 $B_1\text{ xor }B_2\text{ xor }\cdots\text{ xor }B_k=s$ 。求对于每一种选法的 $\gcd(B_1,B_2,\dots,B_k)$ 之和。

$1\leqslant n\leqslant 10^6,1\leqslant k\leqslant 4,1\leqslant A\leqslant 5\times 10^4$

Solution：

首先那个 $\gcd$ 很不好做，考虑莫比乌斯反演把 $\gcd$ 解决掉，设 $g[i]$ 表示最终答案为 $i$ 的方案数，那么答案为： $$ ans=\sum_{i=1}^ng[i]\times i $$ 设 $f[i]$ 表示最终 $\gcd$ 为 $i$ 的倍数的方案数，那么有： $$ f[i]=\sum_{i|d}^ng[d] $$ 由莫比乌斯反演得： $$ g[i]=\sum_{i|d}^n\mu[\frac di]f[d] $$ 那么答案为： $$ ans=\sum_{i=1}^ni\times \sum_{i|d}^n\mu[\frac di]f[d]=\sum_{d=1}^nf[d]\sum_{i|d}\mu[\frac di]i=\sum_{d=1}^nf[d]\varphi[d] $$ 关于异或，我们不难想到 $FWT$ ，在计算 $f[d]$ 的时候，我们可以把所有 $d$ 的倍数都插到数组中，然后把这个数组 $k$ 次幂，得到的 $s$ 那一位的值就是答案。

但是这样单次复杂度为 $m\log m$ 无法通过本题，我们可以用值域分块的方法，对于小于等于 $L$ 的 $d$ ，我们用 $FWT$ 计算，对于其他的 $d$ ， $d$ 的倍数只有不超过 $m/L$ 个，我们可以用 $\text{meet in the middle}$ 来求，复杂度为 $L\times A\log A+(\frac nL)^2$ ，当 $L=\sqrt n$ 时复杂度为 $A\sqrt n log A$ 。

最后由于要求每个数互不相同的方案数，因此要容斥，

Code：