本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}