CF959E Mahmoud and Ehab and the xor-MST 题解【二进制】【贪心】【生成树】

点击量：177

    这个题真是太有意思了ovo

目录

Description

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of \(n\) vertices numbered from \(0\) to \(n-1\). For all \(0\le u<v<n\), vertex \(u\) and vertex \(v\) are connected with an undirected edge that has weight \(u\bigoplus v\) (where \(\bigoplus\) is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer \(n(2\le n\le 10^{12})\), the number of vertices in the graph.

Output

The only line contains an integer \(x\), the weight of the graph’s minimum spanning tree.

Example

input

4

output

4

Note

In the first sample:

The weight of the minimum spanning tree is 1+2+1=4.

题意：

    给定一个编号为\(o\sim n-1\)的带权完全无向图。其中连接\(i\)和\(j\)点的边权值为\(i\bigoplus j\)。求这个图的最小生成树。

题解：

    贪心。因为要生成树，所以每个点都要连一条边到一个比它编号更小的点（这是随机生成树的算法233333）。那么在\(\tt MST\)上，每个点\(i\)连接的边权就是\(\min_{j\in [0,i)}i\bigoplus j\)。

    一个二进制数\(i\)异或一个比它小的二进制数\(j\)所得到的答案最小值是多少呢？应该是它的\(\text{lowbit}\)，因为需要构造出一个值使得\(i\)异或\(j\)\((j<i)\)后的最高位的1最低，如果要求尽可能低又不等于\(i\)，那么最低就是1了，但是如果\(\text{lowbit}(i)\)不是1，那么\(j>i\)就不符合生成树的要求了，可以依此类推到高位直到\(\text{lowbit}\)。

    最高位尽可能低的原理是\(\sum_{i=0}^{k-1}2^i<2^{k}\)，我们要贪心地使最高位的1所在位最低，而因为\((i-\text{lowbit}(i))\bigoplus i=\text{lowbit}(i)\)，则保证了\(j<i\)情况下所得值最小，为\(\text{lowbit}(i)\)，也就是二进制下恰好只有唯一的1。

    所以答案就是\(\sum\limits_{i=0}^{n-1}\text{lowbit}(i)\)。

    然后介绍求法…因为所有的奇数的\(\text{lowbit}\)都是1，所以每两个数就会出现一次\(\text{lowbit}=1\)，同理，每四个数就会出现一次\(\text{lowbit}=2\)。我们现在来分析一个二进制数：

    对于\(10101_{(2)}\)来说，我们现在想知道有多少个比它小的数\(\text{lowbit}=1\)。那么只要满足较高位（即一次右移）小于\(1010\)，并且第0位为1就可以了；要求\(\text{lowbit}=2\)，就要满足第2位及以上的位（两次右移）小于\(101\)，这时要注意如果右移前最后一位是\(1\)，那么它自己也要被算上，比如要求\(\text{lowbit}=4\)，则第3位及以上小于\(10\)，但是如果恰好等于\(10100_{(2)}\)也是合法的，所以每次右移前要判断当前位是否做出贡献。

Code：

#include<cstdio>
int main()
{
    long long n;
    scanf("%I64d",&n);
    n-=1;
    long long ans=0;
    long long base=1;
    while(n)
    {
        ans+=base*(n&1);
        n>>=1;
        ans+=base*n;
        base<<=1;
    }
    printf("%I64d\n",ans);
    return 0;
}