题目背景
上道题中,妖梦斩了一地的木棒,现在她想要将木棒拼起来。
题目描述
有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;
}