CF1922B的题解

（一）

因为 \(2^{n}+2^{n}=2^{n+1}\)。

设取的三个数为 \(2^i\)，\(2^j\)，\(2^k\)，\(i\le j \le k\)。

因为 \(2^i+2^j>2^k\)，所以 \(j=k\)。（反证法易证）

此时 \(i\) 任意取。

注意不要重复取。

将答案分为两类计算，\(i=j=k\) 和 \(i<j=k\)。

（二）

AC 代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,x,sum[300010],ans,s;
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		ans=0,s=0;
		memset(sum,0,sizeof sum);
		for(int i=1;i<=n;i++){
			scanf("%lld",&x);
			sum[x]++;
		}
		for(int i=0;i<=n;i++){
			if(sum[i]>1)ans+=sum[i]*(sum[i]-1)/2*s;
			if(sum[i]>2)ans+=sum[i]*(sum[i]-1)*(sum[i]-2)/6;
			s+=sum[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}