P3799 妖梦拼木棒
又是一道要靠题解的思路的题。（难受）。
解题思路
首先，由于数据大小在5*1e3以内，数据量在1e5以内。所以用桶排记录无疑是最合适的。（记录下数据的最大值和最小值可以提高运行效率）
由题目分析，4个木棒中分三份（每份不为0）必然为1，1，2.
其次，我们用循环i遍历数组b[],取b[i]为三角形的边长（边长不可能是最小值，所以i=min+1），如果b[i]的个数不小于2，那么这个正三角形才有可能成立,当它成立时，我们再用一个循环j从b[min]遍历到b[i/2](把i分为两部分取i小的部分为j，j最大值应该为i/2).b[j]和b[i-j]就是组成b[i]的两部分。当这两部分存在时，分析此时的能组成的正三角形的个数。
最后再把答案相加起来就好了（注意每次加答案时都要对答案取mod）
这里用到数学组合思想
如果当n=2.
组合数=n*(n-1)/2。
当我们知道这个这个数学组合思想后便可以对这个三角形进行分解。
总的可能个数=两个相同的数的组合数*能相加组成与两个相同的数的数的个数。
这样我们就能非常好的计算出再某种情况下正三角形的个数
个人想法
感觉非常秒，数学组合数在n=2时的情况可以直接对数进行运算，如果当n>=3时应该就得通过循环（本人菜鸡还不知道其他方法）来得到组合数的值。可以有效提升计算效率
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 5;
const int M = 1e9 + 7;
int a[N], b[N];
int ans;
int main() {
int n;
cin >> n;
int max = 0;
int min = N;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
b[a[i]]++;
}
for (int i = min + 1; i <= max; i++) {
if (b[i] <= 1) {
continue;
} else {//只有b[i]>=2时才有可能成立。
for (int j = min; j <= i / 2; j++) {
if (b[j] >= 1 && b[i - j] >= 1) {
if (j * 2 == i) {
ans += b[i] * (b[i] - 1) * b[i / 2] * (b[i / 2] - 1) / 4;//这就相当于两个组合数的数相乘
} else {
ans += b[i] * (b[i] - 1) / 2 * b[j] * b[i - j];//两个相同的数的组合数*能相加组成与两个相同的数的数的个
}
}
}
ans %= M;//记得每次都要取mod
}
}
cout << ans % M;
return 0;
}