P10114-题解

· · 题解

题意简述：

给出一个长度为 n 的序列 d，求得：

\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))}

其中定义 \oplus 代表二进制下两数相加的和数位上 1 的个数， \otimes 代表二进制下较大减较小的差数位上 1 的个数。

对于所有数据，n\le 2\times 10^6,\sum{d_i}\le 5\times 10^7。

核心思路：

定义 \operatorname{num}(x) 为 x 二进制下 1 的个数，显然 (d_i\oplus d_j)=\operatorname{num}(d_i+d_j),(d_i \otimes d_j)=\operatorname{num}(\operatorname{abs}(d_i-d_j))，其中 \operatorname{abs}(x) 表示 x 的绝对值。

Sub1

特殊性质：所有的 d_i=1。 化简式子：

\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((1\oplus 1)+(1 \otimes 1))}=\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{(\operatorname{num}(2)+\operatorname{num}(0))} \sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{(\operatorname{num}(2)+\operatorname{num}(0))}=\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}1=n\times n

输出 n \times n，即可。

void sub1(){
    cout<<(long long)n*n<<endl;
    return;
}

Sub2

数据特点：n\le 5\times 10^3。 暴力，枚举每一个 d_i,d_j，计算其贡献，累加在 ans 中，输出答案

int ABS(int x){
    return x<0?-x:x;
}
int num(int x){
    int cnt=0;
    while(x){
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}
void sub2(){
    ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans+=num(d[i]+d[j])+num(ABS(d[i]-d[j]));
        }
    }
    cout<<ans<<endl;
    return;
}

Sub3

特殊性质：d_i 均为 2 的非负整数次幂。

开始动脑子，因为 \sum{d_i}\le 5\times 10^7，而 d_i 均为 2 的非负次幂。说明 d_i 顶多只有不到三十种取值。我们考虑每种取值为答案带来的贡献。

  1. 如果 d_i=2^k,d_j=2^{k'} 且 k\ne k'。那么 \operatorname{num}(d_i+d_j) 的值必然为 2。因为 d_i,d_j 在二进制下只有一个 1，且 1 的位置不相同。

  2. 如果 d_i=2^k,d_j=2^{k'} 且 k=k'。那么 \operatorname{num}(d_i+d_j) 的值必然为 1。因为 d_i,d_j 在二进制下只有一个 1，且 1 的位置相同。相加进位后原来的两个 1 会进位成一个新的 1。

  3. 如果 d_i=2^k,d_j=2^{k'} 且 k=k'。那么 \operatorname{num}(\operatorname{abs}(d_i-d_j)) 的值必然为 0。两个相等的数差为 0，二进制下 1 的个数自然为 0

  4. 如果 d_i=2^k,d_j=2^{k'} 且 k\ne k'。那么 \operatorname{num}(\operatorname{abs}(d_i-d_j)) 的值必然为 \operatorname{abs}(k-k')。可以自己举几个例子尝试一下。

用一个数组 mk_i 表示数组 d 中，2^i 出现的次数，len 表示 d 数组中出现的 2 的最高次幂。则最终答案为：

\sum\limits_{i=0}^{len}mk_i\times(2\times n-mk_i)+\sum\limits_{i=0}^{len}\sum\limits_{j=0}^{len}mk_i\times mk_j\times (i-j)

前面这一堆是上述 1,2 两种情况对答案的贡献，表示有 mk_i 个 2^i，每个 2^i 和其他 mk_i 个数的和在二进制下有一个 1，与 n-mk_i 个数的和有 2 个 1，化简后就是上式。

后面一堆则是 4 这种情况的贡献。就不多赘述了。

void sub3(){
    long long res=0,len=0;
    for(int i=1;i<=n;i++)mk[(int)log2(d[i])]++,len=max((long long)log2(d[i]),len);
    for(int i=0;i<=len;i++)res+=1ll*mk[i]*(2*n-mk[i]);
    for(int i=0;i<=len;i++){
        for(int j=0;j<=len;j++){
            res+=1ll*(mk[i]*mk[j]*ABS(i-j));
        }
    }
    printf("%lld\n",res);
    return;
}

Sub4

令 s=\sum d_i，因为 \sum d_i\le 5\times 10^7，所以哪怕是最坏情况，d_i 不同数的个数也不过在 \sqrt{s} 左右，储存不同种类的数出现的数组 mk，暴力统计即可。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=5e7+10;
int n,mk[N],x;
vector<int>v;
long long ans=0;
int ABS(int x){
    return x<0?-x:x;
}
int num(int x){
    int cnt=0;
    while(x){
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}
int main(){
    scanf("%d",&n);
    v.push_back(0);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(!mk[x])v.push_back(x);
        mk[x]++;
    }
    for(int i=1;i<v.size();i++){
        for(int j=1;j<v.size();j++){
            ans+=(long long)mk[v[i]]*mk[v[j]]*(num(v[i]+v[j])+num(ABS(v[i]-v[j])));
        }
    }
    cout<<ans<<endl;
    return 0;
}

枚举不同种类数的两层循环复杂度 O(s)，内部计算 (\log V)，其中 V 是值域大小。