「2017 山东一轮集训 Day3」第一题 题解

思路

首先注意到组成正方形的方案只有两种：两条边用两根和两条边用一根，或三条边用一根和一条边用三根。

设 $cnt(i)$ 表示数 $i$ 出现的次数。

先考虑如何计算三条边用一根和一条边用三根的方案数。

设组成正方形的四种木棍长度从小到大排序为 $a,b,c,d$，其中 $d$ 用三根，其他用一根，显然有 $d=a+b+c$。

考虑倒序枚举 $b$，然后枚举 $a$，显然符合条件的 $c,d$ 满足 $d-c=a+b$，所以设 $f_i$ 表示当前 $a+b=i$ 时 $c,d$ 的方案数，则此时方案数即为 $f_{a+b}\times cnt(a)\times cnt(b)$。除此之外，还需特判 $b=c$ 或 $a=b$ 或 $a=b=c$ 的情况，方案数分别为 $b=c:\binom{cnt(a+b+c)}{3}\times\binom{cnt(b)}{2}\times cnt(a),a=b:\binom{cnt(a+b+c)}{3}\times\binom{cnt(b)}{2}\times cnt(c),a=b=c:\binom{cnt(a+b+c)}{3}\times\binom{cnt(b)}{3}$。

再考虑如何计算两条边用两根和两条边用一根的方案数。

设组成正方形的五种木棍长度从小到大排序为 $a,b,c,d,e$，其中 $e$ 用两根，其他用一根，显然有 $e=a+d=b+c$。

考虑正序枚举 $d$，然后枚举 $a$，显然符合条件的 $b,c,e$ 满足 $e=b+c=a+d$，所以设 $f_i$ 表示当前 $a+d=i$ 时 $b,c$ 的方案数（还需记录 $b=c$ 的情况），则此时方案数即为 $f_{a+d}\times cnt(a)\times cnt(d)\times\binom{cnt(a+d)}{2}$。除此之外，还需特判 $a=b,c=d$ 或 $a=b=c=d$ 的情况，方案数分别为 $a=b,c=d:\binom{cnt(a)}{2}\times\binom{cnt(c)}{2}\times \binom{cnt(a+d)}{2},a=b=c=d:\binom{cnt(a)}{4}\times\binom{cnt(2a)}{2}$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct N{
	ll v,c;
}a[5010],b[5010];
bool cmp(N a,N b){
	return a.v<b.v;
}
ll mp[10000010],f[10000010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	ll mx=0;
	for(int i=1;i<=n;i++){
		cin>>a[i].v;a[i].c=1;mx=max(mx,a[i].v);
		mp[a[i].v]++;
	}
	sort(a+1,a+1+n,cmp);
	b[1]=a[1];
	int nn=1;
	for(int i=2,j=1;i<=n;i++){
		if(a[i].v==b[j].v)b[j].c++;
		else b[++j]=a[i],nn++;
	}
	n=nn;
	memcpy(a,b,sizeof(a));
	ll ans=0;
	//(a+b+c)+d+d+d
	for(int i=n;i;i--){
		if(a[i].c>2&&a[i].v*3<=mx){//a=b=c
			ll v=mp[a[i].v*3];
			if(v>=3)ans+=v*(v-1)*(v-2)/6*a[i].c*(a[i].c-1)*(a[i].c-2)/6;
		}
		for(int j=1;j<i;j++)if(a[i].v+a[j].v<=mx){
			ans+=f[a[i].v+a[j].v]*a[i].c*a[j].c;
			if(a[i].v*2+a[j].v<=mx&&a[i].c>1&&mp[a[i].v*2+a[j].v]>=3){//b=c
				ll v=mp[a[i].v*2+a[j].v];
				ans+=v*(v-1)*(v-2)/6*a[i].c*(a[i].c-1)/2*a[j].c;
			}
			if(a[j].v*2+a[i].v<=mx&&a[j].c>1&&mp[a[j].v*2+a[i].v]>=3){//a=b
				ll v=mp[a[j].v*2+a[i].v];
				ans+=v*(v-1)*(v-2)/6*a[j].c*(a[j].c-1)/2*a[i].c;
			}
		}
		for(int j=i+1;j<=n;j++)if(a[j].c>=3)f[a[j].v-a[i].v]+=a[i].c*a[j].c*(a[j].c-1)*(a[j].c-2)/6;//记录d-c 
	}
	memset(f,0,sizeof(f));
	//(a+d)+(b+c)+e+e
	for(int i=1;i<=n;i++){
		if(a[i].c>=4&&(a[i].v<<1)<=mx){//a=b=c=d
			ll x=a[i].c,y=mp[a[i].v<<1];
			if(y>=2)ans+=x*(x-1)*(x-2)*(x-3)/24*y*(y-1)/2;
		}
		for(int j=1;j<i;j++)if(a[i].v+a[j].v<=mx&&mp[a[i].v+a[j].v]>=2){
			if(f[a[i].v+a[j].v]){
				ll v=mp[a[i].v+a[j].v];
				ans+=a[i].c*a[j].c*f[a[i].v+a[j].v]*v*(v-1)/2;
			}
			if(a[i].c>=2&&a[j].c>=2){//a=b,c=d
				ll v=mp[a[i].v+a[j].v];
				ans+=a[i].c*(a[i].c-1)/2*a[j].c*(a[j].c-1)/2*v*(v-1)/2;
				
			}
		}
		for(int j=1;j<i;j++)if(a[i].v+a[j].v<=mx)f[a[i].v+a[j].v]+=a[i].c*a[j].c;//记录b+c 
		if(a[i].c>1)f[a[i].v<<1]+=a[i].c*(a[i].c-1)/2;//顺便记录b=c的情况 
	}
	cout<<ans;
	return 0;
}