传送门：https://www.luogu.com.cn/problem/P3799
题目的标签是组合数学和暴力枚举。取四根木棒组成正三角形，显然有两根相等，形成两个边，还有两根（这两根木棒有可能相等也有可能不等）可以组成一条边。那么问题就转化成了在给的数字（即木棒长度）中找到两个相等的数a，然后再找到两个数b和c，使得a=b+c计算所有情况的个数即得到答案。
如果把所有的长度保存在一个数组里来跑双重循环势必会超时，因为最大n达到十万。所以必须想个办法用更小的数组便可以 保存这大量数据，变相减小循环的次数。个人认为这是该题的重要突破口，由于木棒长度小于五千但是最大n为十万，那么就会出现很多重复数字，这样就可以用一个桶的思想，用num[ i ]记录长度为 i 的木棒的个数，这样就有效地减小了循环，也方便了运算。
接下来就是如何跑循环的问题，外层循环为 i ，罗列木棒的所有长度，只要根数超过2就可以进入内层循环，内层循环为 j ，代表组成边的其中一根，另一根长度即为 i-j 。然后用到组合数学的知识计算答案并时刻取模。
上代码：
#include#define MAX ((int)1e9+7)using namespace std;int C(long long n, int m){//求组合数if (m == 1)return n;if (m == 2)return (n * (n - 1) / 2) % MAX;//由于题目中m要么是1要么是2//可以直接用两个判定来处理，判定二记得取模}int main(void){int n = 0, number = 0, ans = 0;int max = 0, num[5005] = { 0 };scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &number);if (number > max) max = number;//记录最长木棒长度num[number]++;}//存储木棒所有长度for (int i = 2; i <= max; i++){if (num[i] >= 2) {for (int j = 1; j <= i / 2; j++){if (i - j == j && num[j] >= 2)ans += (C(num[i], 2) * C(num[j], 2)) % MAX;//i恰好为2*j时else if (i - j != j && num[j] >= 1 && num[i - j] >= 1)ans += ((C(num[i], 2) * C(num[j], 1)) % MAX * C(num[i - j], 1)) % MAX;//记得时刻取余}}ans %= MAX;}printf("%d", ans);return 0;//完结撒花}