CF 959E Mahmoud and Ehab and the xor-MST

题目描述

https://codeforces.com/problemset/problem/959/E

简要题意：给定 $n$ 个点，编号依次为 $[0,n-1]$，对于任意两个点 $u,v$，边 $(u,v)$ 的权值为 $u\oplus v$，其中 $\oplus$ 为异或，求最小生成树

$n\le 10^{12}$

Solution

一个结论，答案为 $\sum_{i=1}^{n-1} i ~\&~ (-i)$，换句话讲点 $i$ 连向点 $i~xor~ (i ~\&~ (-i))$

我们考虑 $Boruvka$，首先第一次连边一定是 $0$ 到 $1$，$2$ 到 $3$，且边权为 $1$

下一次连边的边权为 $2$，在下一次为 $4$，稍微画画大概就能找到规律

正规证明

#include <iostream>
#include <cstdio>
#include <cstring> 
#define ll long long
using namespace std;

ll n; 

ll ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i <= 40; ++i) {
        ll t = n / (1ll << i + 1) + (n % (1ll << i + 1) > (1ll << i));
        ans += (1ll << i) * t;
    }
    cout << ans << "\n"; 
    return 0;
}