P3799 妖梦拼木棒(组合数学)

P3799 妖梦拼木棒

又是一道要靠题解的思路的题。（难受）。

解题思路

首先，由于数据大小在5*1e3以内，数据量在1e5以内。所以用桶排记录无疑是最合适的。（记录下数据的最大值和最小值可以提高运行效率）
由题目分析，4个木棒中分三份（每份不为0）必然为1，1，2.
其次，我们用循环i遍历数组b[],取b[i]为三角形的边长（边长不可能是最小值，所以i=min+1），如果b[i]的个数不小于2，那么这个正三角形才有可能成立,当它成立时，我们再用一个循环j从b[min]遍历到b[i/2](把i分为两部分取i小的部分为j，j最大值应该为i/2).b[j]和b[i-j]就是组成b[i]的两部分。当这两部分存在时，分析此时的能组成的正三角形的个数。
最后再把答案相加起来就好了（注意每次加答案时都要对答案取mod）

这里用到数学组合思想

如果当n=2.
组合数=n*(n-1)/2。

当我们知道这个这个数学组合思想后便可以对这个三角形进行分解。
总的可能个数=两个相同的数的组合数*能相加组成与两个相同的数的数的个数。
这样我们就能非常好的计算出再某种情况下正三角形的个数

个人想法

感觉非常秒，数学组合数在n=2时的情况可以直接对数进行运算，如果当n>=3时应该就得通过循环（本人菜鸡还不知道其他方法）来得到组合数的值。可以有效提升计算效率

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 5;
const int M = 1e9 + 7;
int a[N], b[N];
int ans;

int main() {
	int  n;
	cin >> n;
	int max = 0;
	int min = N;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] > max) {
			max = a[i];
		}
		if (a[i] < min) {
			min = a[i];
		}
		b[a[i]]++;
	}
	for (int i = min + 1; i <= max; i++) {
		if (b[i] <= 1) {
			continue;
		} else {//只有b[i]>=2时才有可能成立。
			for (int j = min; j <= i / 2; j++) {
				if (b[j] >= 1 && b[i - j] >= 1) {
					if (j * 2 == i) {
						ans += b[i] * (b[i] - 1) * b[i / 2] * (b[i / 2] - 1) / 4;//这就相当于两个组合数的数相乘
					} else {
						ans += b[i] * (b[i] - 1) / 2 * b[j] * b[i - j];//两个相同的数的组合数*能相加组成与两个相同的数的数的个
					}
				}
			}
			ans %= M;//记得每次都要取mod
		}
	}
	cout << ans % M;
	return 0;
}