2436: 【普及/提高-】【P3799】妖梦拼木棒
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
有 根木棒，现在从中选 根，想要组成一个正三角形，问有几种选法？
答案对 取模。
输入
第一行一个整数 。
第二行往下 行，每行 个整数，第 个整数 代表第 根木棒的长度。
输出
一行一个整数代表答案。
样例输入 复制
4
1
1
2
2样例输出 复制
1提示
数据规模与约定
- 对于 的数据，保证 。
- 对于 的数据，保证 ，。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long counts[5005] = {0},n,tmp,ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> tmp;
counts[tmp]++;
}
for (int i = 1; i <= 2500; i++) {
for (int j = i; j <= 5000-i; j++) {
int k3=counts[i+j], k1 = counts[i], k2 = counts[j];
if (k3 >= 2) {
if (i == j && k1 >= 2) {
tmp = k1*(k1-1) / 2*k3*(k3-1) / 2 % 1000000007;
ans += tmp;
}
if (i != j && k1 >= 1 && k2 >= 1) {
tmp = k1 * k2 * k3 * (k3-1) / 2 % 1000000007;
ans += tmp;
}
}
}
}
ans %= 1000000007;
cout << ans;
return 0;
}