題目背景

上道題中，小 Y 斬了一地的木棒，現在她想要將木棒拼起來。

題目描述

有?n?根木棒，現在從中選?4?根，想要組成一個正三角形，問有幾種選法？

答案對?109+7?取模。

輸入格式

第一行一個整數?n。

第二行往下?n?行，每行?1?個整數，第?i?個整數?ai??代表第?i?根木棒的長度。

輸出格式

一行一個整數代表答案。

輸入輸出樣例

輸入 #1復制

4 
1
1
2
2

輸出 #1復制

1

說明/提示

數據規模與約定

• 對于?30%?的數據，保證?n≤5×103。
• 對于?100%?的數據，保證?1≤n≤105，1≤ai?≤5×103。

代碼：

#include <bits/stdc++.h>
#define MX 100005
using namespace std;
const int mod = 1e9+7;
int main() {
long long int n,cnt = 0,ant = 0;
cin>>n;
int a[MX],b[MX];
int f[MX] = {0};
for(int i = 1;i <= n;i++)
{
cin>>a[i];
f[a[i]]++;
if(f[a[i]] == 1)
{
b[++ant] = a[i];
}
}
sort(b+1,b+ant+1);
for(int i = 1;i <= ant;i++)
{
if(f[b[i]] >= 2)
{
for(int j = 1;j <= i;j++)
{
if(b[j] > b[i] /2)break;
if(f[b[i] - b[j]] >= 1)
{
if(b[i] - b[j] != b[j])
{
cnt =(cnt + (f[b[i]] *(f[b[i]] - 1)/2*f[b[j]]*(f[b[i] - b[j]]))%mod) % mod;
}
else if(f[b[j]]>=2)
{
cnt = (cnt + ((f[b[i]] *(f[b[i]] - 1)/2 * f[b[j]]*(f[b[j]] - 1)/2)%mod))%mod;
}
}
}
}
}
cout<<cnt;
return 0;
}