妖梦拼木棒
题目背景
上道题中,妖梦斩了一地的木棒,现在她想要将木棒拼起来。
题目描述
有 $n$ 根木棒,现在从中选 $4$ 根,想要组成一个正三角形,问有几种选法?
答案对 $10^9+7$ 取模。
输入格式
第一行一个整数 $n$。
第二行往下 $n$ 行,每行 $1$ 个整数,第 $i$ 个整数 $a_i$ 代表第 $i$ 根木棒的长度。
输出格式
一行一个整数代表答案。
样例 #1
样例输入 #1
4
1
1
2
2
样例输出 #1
1
提示
数据规模与约定
- 对于 $30\%$ 的数据,保证 $n \le 5 \times 10^3$。
- 对于 $100\%$ 的数据,保证 $1 \leq n \le 10^5$,$1 \le a_i \le 5 \times 10^3$。
题解:
思路:要选4根木棍,组成一个正三角形,则易知四根木棍的组成应为L+L+S1+S2
,即两根长的加两根短的,且两根较长的木棍L长度要相等,另外两根较短的S1和S2可能相等也可能不相等,但这两根较短的长度加起来等于较长的木棍
那么思路就是枚举L的长度为i
,然后再枚举S1的长度为j
,则S2就为i - j
设长度为i
的木棍有len[i]
根,则从中选2根的方案数就是C(len[i], 2)
,同理,S1的方案数为C(len[j], 1)
,S2为C(len[i - j], 1)
,根据乘法原理就容易推出以下公式:
按照j == i - j
和j != i - j
两种情况来划分,即S1的长度是否等于S2
情况①(j != i - j
):2L + S1 + S2:
C(len[i], 2) * C(len[j], 1) * C(len[i - j], 1))
情况②(j == i - j
):2L + 2S:
C(len[i], 2) * C(len[j], 2)
枚举所有的长度,每次把上面两种情况的方案数加进ans即可
还有一些边界条件,比如len[i] >= 2
,len[i - j] >= 1 && len[j] >= 1
等需要注意
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5010, mod = 1e9 + 7;
int len[N];
LL ans;
LL C(LL n, LL m)//计算从n个数中选m个数的方案数,m = 1 or m = 2
{
if (m == 1LL) return n;
else if (m == 2LL) return n * (n - 1) / 2;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int tmp, maxn = -1;
while (cin >> tmp)//读入木棒长度,并用数组记录不同长度的木棍数量,并且记录最长的木棒的长度maxn
{
len[tmp]++;
maxn = max(maxn, tmp);
}
for (int i = 2; i <= maxn; i++)//先枚举两根木棒的长度
{
if (len[i] < 2) continue;//当枚举到的长度的木棍不足2根时,跳过这次枚举
for (int j = 1; j <= i / 2; j++)//枚举剩下两根木棍,一根长度为j,另一根长度为i - j
{
if (j != i - j && len[i - j] >= 1 && len[j] >= 1)//当剩下两根木棍不一样长,且两根木棍存在(数量>=1)
{
ans = (ans + C(len[i], 2) * C(len[j], 1) * C(len[i - j], 1)) % mod;
}
else if (j == i - j && len[j] >= 2)//当剩下两根木棍一样长,且数量>=2
{
ans = (ans + C(len[i], 2) * C(len[j], 2)) % mod;
}
}
}
cout << (ans % mod);
return 0;
}