可以看得出来这是一道组合数求解问题。
$30pts$
直接暴力枚举三条边的长度，复杂度为 $Θ(n^3)$。
$50pts$
当所有长度全部相等时，等腰三角形的个数为 $\dbinom{n}{3}$，直接特判输出；其余情况仍然暴力枚举。
$80pts$
题目强调需要构成等腰三角形，我们将所有能组成三角形的分成两类：等边与等腰。
先给输入的木棍的长度去一下重，并记录每一边长的木棍数量。然后将不重复的长度排一个序。对于等边三角形，直接按上述方法求解；对于普通的等腰三角形，两层循环进行枚举，设两条边长为 $b[i],b[j]$ 以及该长度的木棍数量为 $num[i],num[j]$。如果以 $b[i]$ 为腰，则需要满足 $b[i] \times 2 > b[j]$ 且 $num[j] \ge 2$；若以 $b[i]$ 为底，则需要满足 $num[j] \ge 2$ 即可。
则答案有 $\sum^k_{i = 1} \dbinom{num[i]}{3} + \sum^k_{i = 1} \sum^k_{j = i + 1} \dbinom{num[i]}{2} \times num[j] + \dbinom{num[j]}{2} \times num[i]$。($num[i],num[j],b[i],b[j]$ 要确保满足上述条件)
时间复杂度为 $Θ(n^2)$，还有最后一个部分无法通过。
1 | for (int i = 1;i <= k;++i) |
$100pts$
考虑将程序进行优化，用前缀和来维护木棍长度为 $i$ 时，小于等于第 $i$ 根木棍的长度的数量。这样预处理后，时间复杂度就变为 $Θ(n)$。优化后的代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
const int MAX = 200005;
ll vis[MAX << 1],a[MAX],b[MAX],c[MAX][5],s[MAX << 1],ans,n,k;//数组记得开到最大值的 2 倍，否则在计算两边之和是否大于第三边时会 RE
int main ()
{
//用杨辉三角计算组合数
c[0][0] = c[1][0] = c[1][1] = 1;
for (int i = 2;i <= 200000;++i)
{
c[i][0] = 1;//初始化
for (int j = 1;j <= min (i,3);++j) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
scanf ("%lld",&n);
for (int i = 1;i <= n;++i)
{
scanf ("%lld",&a[i]);
if (!vis[a[i]]) b[++k] = a[i];//去重
vis[a[i]]++;//记录数量
}
sort (b + 1,b + 1 + k);//排序
for (int i = 1;i < MAX << 1;++i) s[i] = s[i - 1] + vis[i];//前缀和进行预处理
for (int i = 1;i <= k;++i)
{
if(vis[b[i]] >= 3) ans += c[vis[b[i]]][3],ans %= mod;//等边
ans += c[vis[b[i]]][2] * (s[b[i] * 2 - 1] - vis[b[i]]),ans %= mod;
}
printf ("%lld\n",ans);
return 0;
}
