枚举 数学
本题n
的数据范围太大,只能$o(nlogn)$以内,不显示。但是ai]的数据范围只有5000
,可以根据木棒的长度来枚举。
思路:先选两根长度相同的木棒,再枚举两根长度加起来是i
的木棒,一共两层循环,可以过。
外层循环:从数量大于2
的木棒中选出两根 Cn2
内层循环:从剩余的木棒中取出长度之和为i的木棒,其中一根长度为j
,另一根长度为i - j
,人为规定j <= i - j
,循环判断条件为j <= i / 2
,防止重复枚举
- 接下来分析
j
与i - j
的关系 - 如果
i = i - j
,那么只需要从cnt[j]
中取出两根Ccnt[j] 2
- 如果
i != i - j
,那么从cnt[i]
中取一根,从cnt[i - j]
中取一根,cnt[j] * cnt[i - j]
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5010, mod = 1e9 + 7;
int n, cnt[N];
LL C(int a, int b) {
int res = 1;
for (int i = a, j = 1; j <= b; i -- , j ++ )
res = res * i / j;
return res;
}
int main() {
scanf("%d", &n);
int minv = 1e9, maxv = 0;
for (int i = 0; i < n; i ++ ) {
int x;
scanf("%d", &x);
maxv = max(maxv, x);
minv = min(minv, x);
cnt[x] ++ ;
}
//枚举两根长度相等的边
LL res = 0;
for (int i = minv; i <= maxv; i ++ ) {
if (cnt[i] >= 2) {
LL t = C(cnt[i], 2) % mod;
for (int j = 1; j <= i / 2; j ++ ) {
if (j != i - j && cnt[j] >= 1 && cnt[i - j] >= 1)
res += t * cnt[j] * cnt[i - j] % mod;
if (j == i - j && cnt[j] >= 2)
res += t * C(cnt[j], 2) % mod;
res %= mod;
}
}
}
cout << res << endl;
return 0;
}