CF1922B题解

思路

在不考虑能否构成三角形的情况下，三角形有这几种情况：

1. 三条边的长度各不相等；
2. 等腰，其中腰比底长；
3. 等腰，其中底比腰长；
4. 等边三角形。

题目中木棍的长度都是 $2$ 的幂，我们再对上述几种情况作进一步分析：

1. 无法构成三角形。为了构成三角形，我们要让较短的 $2$ 条木棍尽量长，则三个木棍的长度为 $2^x,2^{x+1},2^{x+2}$，明显构不成三角形。
2. 很明显可以构成三角形。
3. 无法构成三角形。两条腰长度之和最大也只能等于底。
4. 很明显可以构成三角形。

---

实现

经分析只有下面 $2$ 种三角形：

1. 等腰，其中腰比底长；
2. 等边三角形。

于是这么做：

首先桶排，因为 $a_i \le n$，所以可以桶排。

设长度为 $2^x$ 的木棍有 $b_x$ 根，则上述两种三角形的方案数分别为：

1. $\Large\sum_{x=1}^n (C^2_{b_x}\times \sum_{i=1}^{x-1} b_x)$
2. $\Large\sum_{x=1}^n (C^3_{b_x})$

---

code:

#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long

using namespace std;

int t,n,ans;
int a[300002],b[300002],c[300002];

//a 是每个木棍的长度
//b 是桶
//c 是 b 的前缀和

signed main(){
	cin>>t;
	while(t--){
		ans=0;
		memset(b,0,sizeof(b));
		cin>>n;
		for(int i=1;i<=n;++i){
			cin>>a[i];
			++b[a[i]];
		}
		c[0]=b[0];
		for(int i=0;i<=n;++i){
			if(i>0)
				c[i]=c[i-1]+b[i];
			if(b[i]>=2&&i>0)
				ans+=b[i]*(b[i]-1)/2*c[i-1];//1 类三角形的方案数
			if(b[i]>=3)
				ans+=b[i]*(b[i]-1)*(b[i]-2)/6;//2 类三角形的方案数
		}
		cout<<ans<<endl;
	}
}