题目背景
上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。
题目描述
有 nn 根木棒，现在从中选 44 根，想要组成一个正三角形，问有几种选法？
答案对 10^9+7109+7 取模。
输入格式
第一行一个整数 nn。
第二行 nn 个整数，第 ii 个整数 a_iai? 代表第 ii 根木棒的长度。
输出格式
一行一个整数代表答案。
输入输出样例
输入 #1复制
4 1 1 2 2
输出 #1复制
1
说明/提示
数据规模与约定
- 对于 30\%30% 的数据，保证 n \le 5 \times 10^3n≤5×103。
- 对于 100\%100% 的数据，保证 1 \leq n \le 10^51≤n≤105，0 \le a_i \le 5 \times 10^30≤ai?≤5×103。
分析:
这道题....emmm 刚开始没什么思路,看了看题解,大致知道怎么去做了,只是没想到题解是清一色的双重for循环,但是双重循环5000不会超时吗?我记得是双重循环3000+就要超时的.....也或许是大家剪枝用的好吧...
没什么新鲜的东西,四根木棒,假设为a,b,c,d,则必有a+b=c=d,这样组成等边三角形,用桶来存储每个长度短棒的个数,然后开双重for循环,来寻找a和b,找到a和b之后,要看a+b的短棒数量有没有两根,以及a+b是否>5000(题主就是因为没有加这个判断,re了七个数据....),如果都满足的话,还要注意以下两点,若a==b,那么就是长度为a的短棒选两根,长度为2a的短棒选两根,乘积为组合数,如果a!=b,那么就是长度为a的短棒数量*长度为b的短棒数量*长度为a+b的短棒数量,注意要对1e9+7取余,其余没什么了...
上AC代码:
#include<iostream>
#include<math.h>
#include<stdio.h>
#define MODD 1000000007LLusing namespace std;
int n;
int a[100005];
int mark[5005];
int ans;
int CC(int k);
int maxlen=-1;int main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);maxlen=max(maxlen,a[i]);mark[a[i]]++;}for(int i=0;i<=maxlen;i++)for(int j=i;j<=maxlen;j++){if(i+j>5000) break;if(mark[i+j]>0){// cout<<i<<" "<<j<<" "<<mark[i]<<" "<<mark[j]<<endl;if(i==j)ans=(ans+CC(mark[i])*CC(mark[i+i]))%MODD;elseans=(ans+(((mark[i]*mark[j])%MODD)*CC(mark[i+j]))%MODD)%MODD;//cout<<"ans is "<<ans<<endl;}}cout<<ans;return 0;
}
int CC(int k)
{int s=((k*k-k)/2)%MODD;return s;
}