统计不同长度的木棒出现的次数,找到大于等于2次的,从中取两根,作为正三角形的两条边。
找剩余两根木棒,使其长度之和等于正三角形的边
对第一步和第二步用乘法原理得到取法总数。
代码如下:
#include <iostream>
using namespace std;
int a[5010], n, x;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
a[x]++;
}
int ans = 0;
for (int i = 1; i <= 5000; i++)
{
if (a[i] >= 2)
{
int step1 = a[i] * (a[i] - 1) / 2;
int step2 = 0;
for (int j = 1; j <= i/2; j++)
{
if (a[j] && a[i - j] && i != j + j)
{
step2 += a[i - j] * a[j];
}
if (a[j] && i == j + j)
{
step2 += a[j] * (a[j] - 1) / 2;
}
}
ans += step1 * step2;
}
}
cout << ans % 1000000007;
return 0;
}