Luogu p3799 demon dream stick

Portal ：https://www.luogu.com.cn/problem/P3799

The labels of the topics are combinatorics and violent enumeration . Take four sticks to form an equilateral triangle , Obviously, there are two equal , Form two sides , There are two more （ The two sticks may be equal or unequal ） Can form an edge . Then the problem turns into the given number （ That is, the length of the stick ） Two equal numbers found in a, Then find two more numbers b and c, bring a=b+c Calculate the number of all cases to get the answer .

If you save all the lengths in an array to run a double loop, it is bound to timeout , Because the biggest n Up to 100000 . So we must find a way to use a smaller array Save this large amount of data , Reduce the number of cycles in disguise . Personally, I think this is an important breakthrough of the problem , Because the length of the stick is less than fivethousand, but it is the largest n Is 100000 , Then there will be many duplicate numbers , So you can use a bucket of ideas , use num[ i ] The record length is i The number of sticks , This effectively reduces the number of cycles , It also facilitates calculation .

The next question is how to run the cycle , The outer cycle is i , List all lengths of the stick , As long as the number of pieces exceeds 2 You can enter the inner circulation , The inner circulation is j , Represents one of the constituent edges , The other length is i-j . Then use the knowledge of combinatorics to calculate the answer and take the module at any time .

Code up ：

#include<iostream>
#define MAX ((int)1e9+7)
using namespace std;
int C(long long n, int m)
{
	// Find the combination number 
	if (m == 1)return n;
	if (m == 2)return (n * (n - 1) / 2) % MAX;
	// Because in the title m Or 1 Or 2
	// Two decisions can be directly used to deal with , Decision two remember to take the mold 
}
int main(void)
{
	int n = 0, number = 0, ans = 0;
	int max = 0, num[5005] = { 0 };
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &number);
		if (number > max) max = number;
		// Record the longest stick length 
		num[number]++;
	}
	// Store all lengths of sticks 
	for (int i = 2; i <= max; i++)
	{
		if (num[i] >= 2) {
			for (int j = 1; j <= i / 2; j++)
			{
				if (i - j == j && num[j] >= 2)
					ans += (C(num[i], 2) * C(num[j], 2)) % MAX;
				//i It happens to be 2*j when 
				else if (i - j != j && num[j] >= 1 && num[i - j] >= 1)
					ans += ((C(num[i], 2) * C(num[j], 1)) % MAX * C(num[i - j], 1)) % MAX;
				// Remember to withdraw the balance at any time 
			}
		}
		ans %= MAX;
	}
	printf("%d", ans);
	return 0;// End of the flower 
}