当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 洛谷P3799 妖梦拼木棒

洛谷P3799 妖梦拼木棒

2018年02月08日  | 移动技术网IT编程  | 我要评论

新歌试听,失联女教师,重庆市公务员考试网

题目背景

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

题目描述

有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

by-szc

 

果然数学还是自己的短板啊（其实自己什么都很垃圾）

这道题应该是比较裸的组合数问题

枚举短的边，查询长的边

组合数预先处理

 

 

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define LL long long 
using namespace std;
const LL MAXN=2*1e6+10;
const LL mod=1e9+7;
LL N;
LL a[MAXN],h[MAXN];
LL C1(LL a){return a;}
LL C2(LL a){return ( a*(a-1) )/2; }
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else 
    #endif
    LL ans=0;
    scanf("%lld",&N);
    for(LL i=1;i<=N;i++) scanf("%lld",&a[i]),h[ a[i] ] ++;
    for(LL i=1;i<=5000;i++)
        for(LL j=i;j<=5000&&i+j<=5000;j++)
        {
            if(i==j) 
            {
                if(h[i]>=2&&h[i*2]>=2) ans+=C2(h[i])*C2(h[i*2])%mod; 
            }
            else     
            {
                 if(h[i]>=1&&h[j]>=1&&h[i+j]>=2) 
                     ans+=C1(h[i])*C1(h[j])*C2(h[i+j])%mod;
            } 
        }
            
    printf("%lld",ans%mod);
    return 0;
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网