欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3799 妖梦拼木棒

程序员文章站 2022-03-21 19:33:32
题目背景 上道题中,妖梦斩了一地的木棒,现在她想要将木棒拼起来。 题目描述 有n根木棒,现在从中选4根,想要组成一个正三角形,问有几种选法? 输入输出格式 输入格式: 第一行一个整数n 第二行n个整数,a1,a2,……an(0

题目背景

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

题目描述

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