题目背景

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

题目描述

有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_n = C¹_{num [ j ]*}C¹_{num [ n - j ]*}C²_{num [ n ]}

 

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

然后求解即可.

 

代码

 

#include
     
      using namespace std;const int maxn=100008;#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=1;i<=n;i++)    {        scanf("%lld",&a[i]);        num[a[i]]++;        maxl=max(a[i],maxl);    }    for(int i=2;i<=maxl;i++)    {        if(num[i]>=2)        {            for(int j=1;j<=(i/2);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<
      
       <