首页 > 代码库 > luoguP3799 妖梦拼木棒 [组合数学]
luoguP3799 妖梦拼木棒 [组合数学]
题目背景
上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。
题目描述
有n根木棒，现在从中选4根，想要组成一个正三角形，问有几种选法？
输入输出格式
输入格式：
第一行一个整数n
第二行n个整数，a1,a2,……an(0<ai<=5000)，代表每根木棒的长度。
输出格式：
一行一个整数，对1e9+7取模
输入输出样例
输入样例#1：
4 1 1 2 2
输出样例#1：
1
说明
对于30%的数据 N<=5000
对于100%的数据 N<=100000
木棍长度可以用桶存储
考虑枚举长木棍l1和短木棍l2，三角形由两种长度的木棍(l1,l1,l2,l2)或三种长度(l1,l1,l2,(l1-l2))的木棍拼成。
组合数学！
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 typedef long long ll; 7 8 const int maxsiz=5005; 9 const int mod=1e9+7;10 11 int n;12 int buc[maxsiz];13 ll ans;14 15 int C1(int x){16 return x;17 }18 19 int C2(int x){20 return 1ll*x*(x-1)/2%mod;21 }22 23 int main(){24 scanf("%d",&n);25 for(int i=0,tmp;i<n;i++){26 scanf("%d",&tmp);27 buc[tmp]++;28 }29 for(int i=2;i<=5000;i++){30 if(buc[i]>=2)31 for(int j=1;j<=i/2;j++){32 int k=i-j;33 if(k==j){34 if(buc[j]>=2)35 ans=(1ll*C2(buc[i])*C2(buc[j])%mod+ans)%mod;36 }37 else{38 if(buc[j]&&buc[k])39 ans=(1ll*C2(buc[i])*C1(buc[j])*C1(buc[k])%mod+ans)%mod;40 }41 }42 }43 printf("%d\n",ans);44 return 0;45 }
luoguP3799 妖梦拼木棒 [组合数学]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。