P3799 妖梦拼木棒 (组合数学)

题目背景

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

题目描述

有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<bits/stdc++.h>
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<<ans<<endl;
}