P3799 妖梦拼木棒（组合数学）-Toy模板网

这篇具有很好参考价值的文章主要介绍了P3799 妖梦拼木棒（组合数学）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

P3799 妖梦拼木棒

（学习自用）

提交65.01k

通过15.35k

时间限制1.00s

内存限制125.00MB

题目背景

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

题目描述

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

答案对 109+7109+7 取模。

输入格式

第一行一个整数 n。

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

输出格式

一行一个整数代表答案。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

数据规模与约定

对于 30%30% 的数据，保证 n≤5×103。

对于 100%100% 的数据，保证 1≤n≤105，1≤ai≤5×103。

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+7;
const int M=1e9+7;
int num[N];

long long C(int num, int k)//组合数
{
	return k == 1 ? num : num * (num - 1) / 2;
}

int main() {
	int n,a,ans=0,ma=0;
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a;
		ma=max(ma,a);
		num[a]++;
	}
	for(int i=2;i<=ma;i++) {//从2开始，因为要选四条，如果等于1不可能用四个1拼成正三角形 
		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)%M;//边的总数里选两个，拼起来等于边的i-j边总数选两个
				 
				else if(i - j != j && num[j] >= 1 && num[i-j] >= 1)
					ans+=(C(num[i],2)*C(num[j],1))%M*C(num[i-j],1)%M;
					//因为没有每次取模错了好几个测试点。。 
			}
		}
		ans%=M;
	}
	cout<<ans<<endl; 
	return 0;
}

看了这位劳斯的题解：