作业：
组合排列经典四题：
(1)7个不同的球，放6个不同的盒子，要求每个盒子至少放一个球，一共多少种方法?

(2)7个相同的球，放6个不同的盒子，要求每个盒子至少放一个球，一共多少种方法?

(3)7个相同的球，放6个不同的盒子，允许有盒子不放球，一共多少种方法?

(4)7个相同的球，放6个相同的盒子，允许有盒子不放球，一共多少种方法?

小 Y 拼木棒

题目背景

上道题中，小 Y 斩了一地的木棒，现在她想要将木棒拼起来。

题目描述

有 $n$ 根木棒，现在从中选 $4$ 根，想要组成一个正三角形，问有几种选法？

答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

第二行往下 $n$ 行，每行 $1$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 根木棒的长度。

输出格式

一行一个整数代表答案。

样例 #1

样例输入 #1

4 
1
1
2
2

样例输出 #1

1

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 5 \times 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \le 10^5$，$1 \le a_i \le 5 \times 10^3$。

题解：

#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
long long n,x,cnt[5009],ans;
// n：木棒的数量，x:临时存放木棒的长度
// cnt:不同长度的木棒的计数数组，下标代表木棒长度
// ans:累加器，记录符合条件的4根木棒的可能性数量
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){ // 输入木棒长度并且计数
		cin>>x;//输入长度
		cnt[x]++;//计数
	}
	// 假设组成正三角形的四根木棒为A,B,C,D四根木棒，且A>=B>=C>=D
    // 因为要组成正三角形，所以A==B==C+D
	for(int i=2;i<=5000;i++){
// 遍历所有可能组成正三角形四根木棒中相同的两根长木棒 AB
		if(cnt[i]>=2){// 判断选出数量超过2根的木棒长度
			for(int j=1;j<=i/2;j++){// 遍历D木棒，d可能1~A/2
				if(j!=i-j &&cnt[j]&&cnt[i-j])
					// 上面的判断条件有三个
					// 1、C不等于D
					// 2、D木棒存在
					// 3、C木棒存在
					// 满足这三个条件就进行排列组合计数
					// cnt[i]*(cnt[i]-1)/2 长度等于i的木棒中取两根有多少种情况
					// cnt[j]*cnt[i-j] 取一根长度为j的木棒和取一根长度为i-j的木棒有多少种情况
					ans=(ans+cnt[i]*(cnt[i]-1)/2*cnt[j]*cnt[i-j])%MOD;
				if(j==i-j && cnt[j]>=2)
					ans=(ans+cnt[i]*(cnt[i]-1)/2*cnt[j]*(cnt[j]-1)/2)%MOD;
			}
		}
	}
	cout<<ans;
	return 0;
}