P3799 妖梦拼木棒-526互联

当然这是我第一次写博客,我在我自己的笔记上面不知道写多少注释加理解了,一直苦于找不到博客;

蒟蒻第一次开始系统性的刷题,没想到第二道就遇到了排列组合的数学题,可恶啊,还是被一个六年级的小学生教会的;

# 妖梦拼木棒

## 题目背景

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

## 题目描述

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

答案对 10^9+7取模。

## 输入格式

第一行一个整数 $n$。

第二行往下 $n$ 行，每行 $1$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 根木棒的长度。

## 输出格式

一行一个整数代表答案。

## 样例 #1

### 样例输入 #1

```
4
1
1
2
2
```

### 样例输出 #1

```
1
```

接下来上代码:

#include<bits/stdc++.h>
#define ll long long//定义long long 减少码量
using namespace std;
const ll N=1e6+10,mod=1e9+7;
ll n,ans,maxx=-1,minn=0x3f3f,num[N];//num数组记录长度为a的木棍的数量;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        ll a;
        cin>>a,num[a]++;
        maxx=max(maxx,a);//找出长度的最大值和最小值
        minn=min(minn,a);
    }
    for(int i=minn+1;i<=maxx;i++)//开始从最小+1遍历,为什么不是minn?
    //因为如果是minn的话,是不可能用4个木棍拼接成功的,相同长度的木棍只能用3个拼接
    {
        if(num[i]>=2)//如果相同长度的木棍超过两个了,说明接下来的两个其他长度的木棍就有可能形成一次拼接
        {
            for(int j=minn;j<=i/2;j++)//防止重复计算,就从i/2结束了;
            {
                //接下来的是重要代码,考察小学(高中)知识,排列组合从n个里面选2个和从n个里面选1个都是可以自己推导出公式的
                //因为选的数量很小,很好推,如果是1个,那就是n,如果是取两个,那就是(1/2*n*n-1),自己参考高中排列组合;
                if(j!=i-j) ans+=num[i]*(num[i]-1)*num[j]*num[i-j]/2,ans%=mod;
                //如果这两个木棍长度不一样,那么就是从j长度的木棍中取一个,从i-j的长度中取一个;
                else if(num[j]>=2&&2*j==i) ans+=num[i]*(num[i]-1)*num[i/2]*(num[i/2]-1)/4,ans%=mod;
                //如果长度一样,先判断这个长度木棍是否够两个,然后再取,注意每次都要取模
            }
        }
    }
    cout<<ans;
}