E. Mahmoud and Ehab and the xor-MST dp/数学/找规律

题意

给出一个完全图的阶数n(1e18)，点由0---n-1编号，边的权则为编号间的异或，问最小生成树是多少

思路

由于一个数k和比他小的数异或，一定可以取到k与所有正整数形成的异或值的最小值。这里简单得形式化证明一下 假设一个数为1000110 那么他的最佳异或和为010（即留下最靠近右边的1其他全部置0) 我们定义\(lsb(x)=x\And(-x)\)由字符形的变量编码我们可以知道，这就可以取得x最右边的那个值 所以只要从小到大加点，每次加一个点的时候，选取比它小的编号的点和它异或的最小边相连，一定可以构成最小的生成树每次加的边都是\(lsb(x)\)
所以计算为 \(\sum_{i=0}^{n-1}lsb(i)\) 现在考虑的就是如何优化了，因为n<=1e18，盲猜\(O(logn)\)复杂度

数学法

设\(f(x)\)为整数y满足\(1<=y<=n\)并且\(lsb(y)=x\)的数有多少，所以\(\sum_{i=1}^{n}lsb(i)=\sum_{i=1}^{n}i×f(i)\)由当且仅当i为2的幂的时候f(x)>0所以公式转化成\(\sum_{i=1}^{log(n)}f(2^i)*2^i\) 而由二进制由4举例 100 1100 11100 我们可以看出 每次取4的边都是要100的后缀所以1000就是其循环节 也就是2*(lsb(i));所以我们也就可以利用这个性质求出\(f(x)=\lfloor(n-x)/(2*x)\rfloor+1\) \(1<=x<=n\)x为\(2^k\)

dp法

由取边的大小\({1}->{1,2,1}->{1 ,2 ,1 ,4 ,1 ,2 ,1 ,8 ,1 ,2 ,1, 4, 1, 2, 1}\)
设f(x)=\(\sum_{i=1}^{x}lsb(x)\) 并设\(dp[i]=f(2^i-1)\)由上面的规律我们们可以看出\(dp[i]=2*dp[i-1]+2^{i-1}\)}即每次增加\(2^i-1\)个，都是左右复制一下上一个\(2^{i-1}-1\)然后中间多一个\(2^{i-1}\) 所以如果取点的数量是\(2^k\)的，就直接可以通过其算出来，那不是\(2^k\)长度的怎么办呢？我们将其分成两个部分\(f(x)=f(msb(x))+f(msb(x)\bigoplus x )\)
msb表示只取该数二进制位最右边的值，也就是前面说的\(2^k\)，可以直接通过dp数组求出来，而剩下那部分,我们可以递归求解重复分界部分，这样分解到最后 其实就是n的每一位如果是1 那么就加上对应的这部分的值，例如\(f(1101_2)=f(1_2)+f(100_2)+f(1000_2))\)

数学法

#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int> 
typedef long long ll;
using namespace std;
const int maxn=2e6+200;
int main(){
    ll n,ans=0;
    scanf("%lld",&n);
    n--;
    for(ll i=1;i<=n;i<<=1)
        ans+=((n-i)/(i*2)+1)*i;//每个值都是2的不同幂产生的 值为lsb(a&(-a));即取最小位的1的值
    printf("%lld\n",ans);

    return 0;
}

dp法

#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int> 
typedef long long ll;
using namespace std;
const int maxn=2e6+200;
ll dp[200];
int main(){
    ll n,ans=0;
    scanf("%lld",&n);
    n--;
    for(int i=1;i<40;i++){
        dp[i]=2ll*dp[i-1]+(1ll<<(i-1));
    }
    for(int  i=0;i<40;i++){
        if(n&(1ll<<i))ans+=dp[i]+(1ll<<i);
    }
    cout<<ans<<endl;

    return 0;
}