打卡信奥刷题（3410）用C++实现信奥题 P10114 [LMXOI Round 1] Size

rogeliu

411人浏览 · 2026-06-27 12:03:32

rogeliu · 2026-06-27 12:03:32 发布

P10114 [LMXOI Round 1] Size

题目背景

在漆黑的夜晚，魔女带走了 LMX，HQZ 为了拯救 LMX。要完成魔女给出的任务。

题目描述

魔女给出一个长度为 $n$ 的序列 $d$ ，魔女想要求得：

$∑i=1n∑j=1n((di⊕dj)+(di⊗dj))\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$ 表示序列的长度。

第二行 $n$ 个非负整数，表示序列 $d$ 。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

2
1 3

输出 #1

输入输出样例 #2

输入 #2

10
114514 19 19 810 1477 44151 15260 369 2010 222

输出 #2

说明/提示

样例解释 #1

如下表所示，因此答案为 $1 + 2 + 2 + 2 = 7$ 。

$i$	$j$	$an s$
$1$	$1$	$1$
$1$	$2$	$2$
$2$	$1$	$2$
$2$	$2$	$2$

对于 $\%$ 的数据，保证 $\le n\le 2\times 10^6,\sum\limits d_i\le5\times10^7$ 。

子任务编号	$n$	特殊性质	分值
Subtask #1	$\le 2\times10^6 $	$d_i =1$	$10$
Subtask #2	$≤5000\le 5000$	无	$20$
Subtask #3	$≤2×106\le 2\times 10^6$	$d_i$ 是 $2$ 的次幂	$30$
Subtask #4	$≤2×106\le 2\times 10^6$	无	$40$

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e7+5;
template<typename T>inline void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')
		f=-1;c=getchar();}
    while(isdigit(c)) 
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=f;
}
int n,cnt[N],d,a[N],len;
long long ans;
inline int calc(int x){
    int res=0;
    while(x) 
		++res,x-=x&-x;
    return res;
}
int main(){
    read(n);
    while(n--){
        read(d);
        if(cnt[d]++==0) a[++len]=d;
    }
    for(int i=1;i<=len;++i)
        for(int j=1;j<=len;++j)
            ans+=1ll*cnt[a[i]]*cnt[a[j]]*(calc(a[i]+a[j])+calc(abs(a[i]-a[j])));
    printf("%lld",ans);
    return 0;
}