洛谷P3799 妖梦拼木棒

2018-06-17 21:15:04来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

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

题目描述

有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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++多重继承的构造执行顺序

下一篇:用非递归方法实现共享表运算