妖梦拼木棒
题目背景
上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。
题目描述
有 (n) 根木棒，现在从中选 (4) 根，想要组成一个正三角形，问有几种选法？
答案对 (10^9+7) 取模。
输入输出格式
输入格式
第一行一个整数 (n)。
第二行 (n) 个整数，第 (i) 个整数 (a_i) 代表第 (i) 根木棒的长度。
输出格式
一行一个整数代表答案。
输入输出样例
输入样例 #1
4
1 1 2 2
输出样例 #1
1
说明
数据规模与约定
- 对于 (30\%) 的数据，保证 (n le 5 imes 10^3)。
- 对于 (100\%) 的数据，保证 (1 leq n le 10^5)，(0 le a_i le 5 imes 10^3)。
分析
首先，四根木棍要拼成正三角形，不难想到只有一种可能：两根木棍的长度相等，另外两根的长度和也和前面那两根木棍长度相等。
为了方便起见，我们把木棍从大到小长度命名为(w, x, y, z)，此时就有(w = x = y + z)。
那么此题的思路也就比较好想了，采用桶计数思想，记录每个长度出现的次数，然后枚举每一种可能的长度作为(w, x)，然后再在二层循环中枚举和为前两根木棍长度(w)（(x)也等效，因为(w = x)）的木棍(y, z)，然后再用乘法原理，组合数来计算新方案。同时，我们还设桶计数思想中的这个桶数组为(a)，也就是说，(a_i)代表长度为(i)的木棍数量。
但还是这个具体怎么计算呢？分为两种情况。
- (y ot= z)：这种情况就是在长度为(w)（(x)）取(2)根的方案数( imes)长度为(y)的木棍中取(1)根的方案数( imes)长度为(z)的木棍中取(1)根的方案数。因为(y ot= z)，长度为(y)的木棍中取(1)根的方案数和长度为(z)的木棍中取(1)根的方案数之间可以直接画乘号（互不干涉性）。这种方案的公式就是(C^2_{a_w} imes C^1_{a_y} imes C^1_{a_z})。
- (y = z)：这种情况就是在长度为(w)（(x)）取(2)根的方案数( imes)长度为(y)（(z)）的木棍中取(2)根的方案数。这次(y = z)了，我们要放在一个地方中考虑。用公式表示就是(C^2_{a_w} imes C^2_{a_y})
讲完思路，我们就上代码咯。
代码
/*
* @Author: crab-in-the-northeast
* @Date: 2020-04-06 00:25:54
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2020-04-06 10:23:32
*/
#include <iostream>
#include <cstdio>
#include <climits>
typedef long long ll;
const int mod = 1e9 + 7;
const int maxl = 5e3 + 5;
int a[maxl];
inline int max(int a, int b) {
return a > b ? a : b;
}
inline int min(int a, int b) {
return a < b ? a : b;
}
int main() {
int n;
ll ans = 0;
std :: cin >> n;
int begin = INT_MAX;
int end = INT_MIN;
for(int i = 1; i <= n; i++) {
int len;
std :: cin >> len;
begin = min(begin, len);
end = max(end, len);
a[len]++;
}
for(int i = begin + 1; i <= end; i++) {
if(a[i] > 1) {//数量必须>1，要不然凑不成前面的两根木棍
for(int j = begin; j <= i / 2; j++) {
if(a[j] && a[i - j]) {//看看是不是都有
if(j == i - j && a[j] >= 2)//如果两个是相等的，还需要注意这个够不够两根
ans = ans + ((a[i] * (a[i] - 1) >> 1) * (a[j] * (a[j] - 1) >> 1) % mod) % mod;
else if(j != i - j)//要特别注意这个if，因为上边的条件中如果j == i - j但是a[j] < 2仍然会来到这个分支，所以我们必须保证j != i - j才能进行下一步计算
ans = ans + ((a[i] * (a[i] - 1) >> 1) * a[j] * a[i - j]) % mod;
}
ans %= mod;
}
}
}
std :: cout << ans << std :: endl;
return 0;
}