即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

拼三角形

编程语言 qq_31640513 11℃ 0评论

【题目描述】


给你n根木棍,用4根木棍能拼出多少个正三角形呢?


【输入格式】


第一行一个整数n


第二行n个整数Ai表示第i根木棍的长度。


【输出格式】


正三角形的个数。


答案可能很大,请对109+7取模。


【样例输入】


4


1 1 2 2


【样例输出】


1


【数据范围】


对于10的数据,满足1<=n<=10


对于50的数据,满足1<=n<=103


对于100的数据,满足1<=n<=106,且0<=Ai<=5000


【分析】


不难想到这4根木棍只能这么分布:x,y,x+y,x+y。


于是枚举Ai,用组合数公式计算即可,注意一些细节。

#include
using namespace std;
int a[5005]={0};
const int Mod=1e9+7;
int main(){
    int n,x,Max=0,ans=0;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&x),a[x]++,Max=max(Max,x);
    for (int i=2;i<=Max;i++){
        int t=a[i]*(a[i]-1)/2;
        for (int j=1;j<=i/2;j++)
            if (j!=i-j) ans=(ans+t*a[j]*a[i-j])%Mod; else ans=(ans+t*a[j]*(a[j]-1)/2)%Mod;
    }
    printf("%d",ans);
}

转载请注明:CodingBlog » 拼三角形

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情