P10114

zibenlun · 2024-01-28 20:40:09 · 题解

思路

看到 100% 的数据范围很吓人对吧，不过经过优化的 n^2 的时间复杂度也是可以完成的。

暴力的方法不细说，就是直接按照题目要求模拟一下。

再看子任务三，d_i 是 2 的次幂，众所周知，指数的增长是非常快的，即使在长整型中也只有不到 64 次，所以一定会有很多重复。针对这个特性我们可以想到把相同的值只保留一个并统计个数，之后在计算的过程中，对于每一个 (i,j) 我们在统计一遍的个数上乘上 d_i 和 d_j 的个数。

对于全部的数据其实差不多，也是子任务三的思路，但是要加上一点点优化。我们能发现，对于不等的一对 (i,j) ,实际上 (i,j) 与 (j,i) 时的结果相同，那么我们只统计一次再乘二就可以了。

CODE

#include<bits/stdc++.h>
using namespace std;
inline __int128 read() {
    __int128 s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s;
}
#define lowbit(x) (x&(-x))
inline void write(__int128 x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
long long n,a[2000005];
__int128 ans;
bool cmp(int x,int y){
    return x>y;
}
map<long long,int> mp,vis;
int main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();
    int m=n;
    for(int i=1;i<=m;i++){
        a[i]=read();
        if(mp[a[i]]>=1){
            m--;
            i--;
            mp[a[i+1]]++;
            continue;
        }
        mp[a[i]]=1;
    }
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j++){
            long long x=a[i]+a[j],sum=0;
            while(x) x-=lowbit(x),sum+=1+(i!=j);
            x=a[i]-a[j];
            if(x<0) x=-x;
            while(x) x-=lowbit(x),sum+=1+(i!=j);
            ans+=sum*mp[a[i]]*mp[a[j]];
        }
    }
    write(ans);
    return 0;
}