题目背景

上道题中,妖梦斩了一地的木棒,现在她想要将木棒拼起来。

题目描述

有n根木棒,现在从中选4根,想要组成一个正三角形,问有几种选法?

输入输出格式

输入格式:

第一行一个整数n

第二行n个整数,a1,a2,……an(0<ai<=5000),代表每根木棒的长度。

输出格式:

一行一个整数,对1e9+7取模

输入输出样例

输入样例#1:

4 1 1 2 2
输出样例#1:

1

说明

对于30%的数据 N<=5000

对于100%的数据 N<=100000

Solution

很显然这是个数学水题,我都会做...

因为是要找 4 根小木棍.

所以很显然这个正三角形的组成是:

n1 , n2 , n1+n2 , n1+n2;

所以公式就是 :

Ans = CCC

其中,num数组代表当这种长度的木板所有的数量.然后 j 为 从 1 枚举到 n/2 .

然后求解即可.

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=;
#define ll long long
#define mo 1000000007
#define C1(x) (x)
#define C2(x) ((x)*((x)-1)/2)
ll n,maxl,ans;
ll num[maxn],a[maxn];
int main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
num[a[i]]++;
maxl=max(a[i],maxl);
}
for(int i=;i<=maxl;i++)
{
if(num[i]>=)
{
for(int j=;j<=(i/);j++)
{
ll k=i-j;
if(k!=j)
ans+=(C1(num[j])%mo)*(C1(num[k])%mo)*C2(num[i])%mo;
else
ans+=(C2(num[j])%mo)*(C2(num[i])%mo)%mo;
ans%=mo;
}
}
}
cout<<ans<<endl;
}
05-11 19:33