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

题目背景

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

题目描述

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

输入输出格式

输入格式：

第一行一个整数n

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

输出格式：

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

输入输出样例

输入样例#1：

4 1 1 2 2

输出样例#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=;

#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;

}

巴特西