P3799 妖梦拼木棒
- 53通过
- 345提交
- 题目提供者orangebird
- 标签
- 难度普及/提高-
- 时空限制1s / 128MB
提交 讨论 题解
最新讨论更多讨论
- 暂时没有讨论
题目背景
上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。
题目描述
有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
吐槽：做这道题发现了我个人的很多问题，做题实在是不够仔细！
分析：假设选4根木棍长度为a=b=c+d,我们枚举a和c,就能计算出b和d,这就变成了从所给长度中能选出多少根我们枚举长度的木棍，就要用到组合数。需要注意的是，我们要特判c是否等于d,因为选择一根c长度的木棍的方案数*选择一根d长度木棍的方案数≠选择两根c长度木棍的方案数，同时，枚举c到a/2就一定要停止，因为超过a/2,就会把一个答案算2次。关于取模的问题，其实我们只需要用到两个组合数,这两个组合数在计算的时候都不必取模，为什么呢？因为5000*4999/2 < 1e9 + 7,如果非要取模，就只有用逆元了。
如果是用数学方法做这种统计方案数的题一定要非常细心！注意所有可能但不完全相同的情况并且不能多算少算！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std; const int mod = ; int n;
long long a[],maxn,ans; LL c1(LL x)
{
return x;
} LL c2(LL x)
{
return x * (x - ) / ;
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
long long t;
scanf("%lld", &t);
maxn = max(maxn, t);
a[t]++;
}
for (int i = ; i <= maxn; i++)
for (int j = ; j <= i/; j++)
{
int b = i - j;
if (b != j)
{
if (a[i] >= && a[b] >= && a[j] >= )
ans += (c2(a[i])*(c1(a[j]) % mod)) % mod*(c1(a[b]) % mod) % mod;
}
else
{
if (a[i] >= && a[j] >= )
ans += c2(a[i])*c2(a[j]) % mod;
}
ans %= mod;
}
printf("%lld\n", ans % mod); return ;
}