luogu3799 妖梦拼木棒

题目大意

有n根木棒，现在从中选4根，想要组成一个正三角形，问有几种选法？木棒长度都<=5000。

题解

根据容斥原理，三角形两条边分别由长度相等的单根木棒组成，另一条边由两条小于该边长的木棒构成。由此想到了乘法原理。我们设置一数组$a$记录长度为$i$的木棒有多少个，则对于一个边长$e$，选两条单边有$C_{a_e}^2=\frac{a_e(a_e -1)}{2}$种选法，另外两条构成一条边的木棍有$\sum_{i+j=e}a_i a_j$。像这样枚举即可。

#include <cstdio>

#include <cstdarg>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

#define ll long long

#define ModMult(x, y) (x * y % P)

#define ModPlus(x, y) ((x + y) % P)

#define Comb2(x) (x * (x - 1) / 2 % P)

const int MAX_VAL_RANGE = 5010;

const ll P = 1e9 + 7;

ll ValCnt[MAX_VAL_RANGE];

int main()

{

	int n;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)

	{

		int x;

		scanf("%d", &x);

		ValCnt[x]++;

	}

	ll ans = 0;

	for (int i = 1; i <= 2500; i++)

	{

		ans = ModPlus(ans, ModMult(Comb2(ValCnt[i]), Comb2(ValCnt[i * 2])));

		for (int j = i + 1; j <= 5000 - i; j++)

			ans = ModPlus(ans, ModMult(ModMult(ValCnt[i], ValCnt[j]), Comb2(ValCnt[i + j])));

	}

	printf("%lld\n", ans);

	return 0;

}