题意简述
给定一个长度为 \(n\) 的序列,求 \(\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))}\)。
思维路径
观察数据范围可以发现 \(n\le 2\times 10^6\) 而 \(\sum\limits d_i\le5\times10^7\),这说明 \(d\) 数组中的重复值较多,直接枚举数值可以减少很多重复计算量。
对于重复值只要在计算时乘上对应的数量即可
AC 代码
代码中附了暴力的代码和正解的代码,注意分辨。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2000009;
ll n,d[N],ans,f[N],vl[N],nV;
void input(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>d[i];
}
ll cal(ll x){
ll cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
return cnt;
}
void solveBF(){
for(ll i=1;i<=n;i++){
for(ll j=i;j<=n;j++){
ll cnt=0;
// cout<<cal(d[i])<<" "<<cal(d[j])<<" "<<cal(d[i]+d[j])<<" "<<cal(abs(d[i]-d[j]))<<"\n";
cnt+=cal(d[i]+d[j]);
cnt+=cal(abs(d[i]-d[j]));
if(i==j) ans+=cnt;
else ans+=cnt*2;
}
}
cout<<ans;
}
void solve(){
sort(d+1,d+n+1);
if(d[n]==1){
cout<<n*n;
return;
}
for(ll i=1;i<=n;i++){
if(d[i]!=d[i-1]) vl[++nV]=d[i];
f[nV]++;
}
for(ll i=0;i<=nV;i++){
ans+=f[i]*f[i]*cal(vl[i]);
for(ll j=i+1;j<=nV;j++){
ans+=f[i]*f[j]*(cal(vl[i]+vl[j])+cal(vl[j]-vl[i]))*2;
}
}
cout<<ans;
}
int main(){
input();
if(n<=5000)
solveBF();
else
solve();
return 0;
}
标签:代码,cnt,洛谷,limits,题解,ll,P10114,sum
From: https://www.cnblogs.com/lemon-cyy/p/17994145