P3799 妖梦拼木棒

题目大意：

有n根棍子，用四根棍子拼成一个正三角形，有几种拼法。

• 对于 30%30% 的数据，保证 n≤5×10^3。

• 对于 100%100% 的数据，保证1≤n≤10^5，1≤ai≤5×10^3。

思路：

由于是拼成正三角形，三条边相等，所以是这样的三角形：

有一条边会分为两个部分，这两个部分的和是另外的边，而且棍子的长度很短，所以我们可以枚举另外两条边的长度，然后再计数。

如何计数：首先我们需要知道

A(n,m)=n*(n-1)*(n-2)……（n-m+1)，也就是由n往下每个数连乘。

C（n,m）=A(n,m)/A(m,m)。一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。

我们假设另外两条边为t，分成的两部分是n,m，tot[i]表示i出现的次数。

如果n!=m,n和m的组合有tot[n]*tot[m]种(加乘原理)，再考虑另外两条边，种数就有C(tot[n+m],2)，因为他是从tot[n+m]种数中选2个。

如果n=m，n和m的组合，因为n=m，所以是从tot[n]中选两个，种数就有C(tot[n],2)，然后另外两条边一样。

记得对1e9+7取模！！！

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[100001],sum,t[5001],maxn=LONG_LONG_MIN;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        t[a[i]]++;
        maxn=max(a[i],maxn);
    }
    for(int i=2;i<=maxn;i++){
        if(t[i]>=2){
            for(int j=1;j<=i/2;j++){
                if(i-j!=j){
                    if(t[j]&&t[i-j]){
                        sum+=(t[j]*t[i-j])*(t[i]*(t[i]-1)/2);
                        sum%=mod;
                    }
                }else{
                    if(t[j]&&t[i-j]){
                        sum+=(t[j]*(t[j]-1))/2*(t[i]*(t[i]-1)/2);
                        sum%=mod;
                    }
                }
            }
        }
    }
    cout<<sum;
    return 0;
}