§ Description

Link.

一完全图有 $n$ 个节点 $0,...,n-1$，其中边 $(i,j)$ 的权值为 $i\oplus j$，其中 $\oplus$ 为位异或操作，试求出最小生成树的边权和。

§ Solution

先从递推的层面考虑.

我们定义 $F(n)$ 表示结点数为 $n$ 的答案，也就是最小生成树的边权和.

首先边界条件为 $F(0)=0,F(1)=1$.

然后我们考虑如何从 $F(n-1)$ 推到 $F(n)$.

每当我们新加入一个结点 $n-1$（题目结点编号从 0 开始），它的点权为其本身，也就是 $n-1$，那么此时我们就要从之前的 $n-1$ 个结点中选出一个点与 $n-1$ 相连构成当前的最小生成树.

因为边 $(u,v)$ 的边权 $w(u,v)=u\ \mathrm{xor}\ v$ 且图为完全图，所以我们每加入一个新结点 $n-1$ 时，所有我们之前的 $0\cdots n-2$ 号结点都可以被选择.

那么问题转化为：对于一个数 $n-1$，我们需要选出一个整数 $x\in[0,n-1)$ 使得 $(n-1)\ \mathrm{xor}\ x$ 最小.

考虑异或运算的定义：每一位相同为零，不同为一.

那么我们选出的 $x$，需要满足二进制意义下每一位和 $n-1$ 尽量相同，并且从右到左（也就是二进位从低到高）的第一个不同的位置尽量低.

那么结论就摆在眼前了，我们选择的这个 $x$ 为 $(n-1)-\mathrm{lowbit}(n-1)$.

为什么？想想 $\mathrm{lowbit(x)}$ 操作的定义：二进制下 $x$ 最低的 1 和后面的 0 组成的二进制数.

这样结论的正确性就显然了.

我们 $F(n)$ 的递推公式为 $F(n)=F(n-1)+(n\ \mathrm{xor}\ (n\ \mathrm{xor}\ \mathrm{lowbit}(n)))$.

那么暴力递推的代码如下：

（code？）

#include<bits/stdc++.h>
using namespace std;
long long f[100005];
signed main()
{
    long long n;
    scanf("%lld",&n);
    f[0]=0;
    f[1]=1;
    for(long long i=2;i<n;++i)   f[i]=f[i-1]+(i^(i^(i&-i)));
    printf("%lld\n",f[n-1]);
    return 0;
}

仔细观察一下递推式，$n\ \mathrm{xor}\ (n\ \mathrm{xor}\ \mathrm{lowbit}(n))$ 不就是 $\mathrm{lowbit}(n)$ 嘛！

那么为题转化为求 $\mathrm{lowbit}$ 前缀和.

通过打一个 $\mathrm{lowbit}$ 表的方法，我们发现 $\mathrm{lowbit}$ 的值十分有规律，就像这种形式：

$$\texttt{1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32}\cdots$$

其实这种规律要证明也很方便，只要根据二进制数末尾的情况即可得知.

虽然这个规律没啥用，但是启发了我们按位统计贡献的方法在 $\Theta(1)$ 空间 $\Theta(\log_{2}n)$ 的时间内计算出了 $\mathrm{lowbit}$ 前缀和.

具体方法请参考代码.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
signed main()
{
    LL n;
    scanf("%lld",&n);
    LL ans=0,app=1,low=n;
    while(low>1)  ans+=app*(low>>1),low-=(low>>1),app<<=1;
    printf("%lld\n",ans);
    return 0;
}