题解 P3799 【妖梦拼木棒】
灵乌路空
2019-07-09 17:52:05
知识点:组合数学，暴力枚举
[原题面](https://www.luogu.com.cn/problem/P3799)
$\text{Rewrited on 2020.6.14.}$
感谢 [TheStars](https://www.luogu.com.cn/user/247889) 发现错误，并提出宝贵意见。
## 题目要求
有 $n$ 根木棒，Yoomu 现从中选 4 根。
求组成一个正三角形的方案数。
---
## 分析题意
欲由4根木棒组成一个正三角形，则必有 **2根长度相等**。
且另外2根长度之和，等于 **前2根相等的木棒 的长度**。
发现 各木棍 的长度 $a_i \leq 5000$，时间复杂度 $O(n^2)$ 可过。
考虑直接用两层循环，**暴力枚举** 上述两种木棒的长度，计算方案数并累加。
---
## 感性理解
记 $num_i$ 为，长度为 $i$ 的木棒的个数。
### 外层循环:
先要从 许多长度为 $i$ 的木棒 中取出2根 ,
方案数为 从 $num_i$ 个数中取出2个数的组合，即$C(num_i,2)$。
### 内层循环:
要从 剩余的木棒中 取出2根长度之和为 $i$ 的木棒。
令其中一根长度为 $j$，则另一根长度为 $i-j$。
显然有 $1\le j<i$，$1\le i-j < i$。
讨论 $j$ 与 $i-j$ 的关系：
1. 若 $j=i-j$：
即从长度为 $j$ 的木棒中取出2根 合成一条边。
方案数为 从 $num_j$ 个数中取出2个数的组合，即 $C(num_j,2)$。
2. 若 $j \not= i-j$：
需从长度为 $j$ 和 $i-j$ 的木棒中各取出1个。
根据乘法原理，则方案数为 $C(num_j,1) \times C(num_{i-j},1)$
根据乘法原理，将所有方案数相乘，即得 $ans$ 的增量 。
---
## 算法分析:
定义计数数组 $num[i]$，记录长度为 $i$ 的木棒的个数。
在读入长度时求得 $num[i]$的值。
### 外层循环:
枚举两根相等的木棒的长度 $i$ ,
为保证可构成三角形，此长度的木棒数量 $\ge 2$ 时才可进入内层循环。
### 内层循环:
枚举一根用来合成的木棒长度 $j$，另一根长度即为 $i-j$。
为保证不重复计算，强制要求 $j\le i-j$，枚举 $j$ 时到$\dfrac{i}{2}$ 停止。
分上述两种情况讨论:
1. 若 `(j == i - j && num[j] >= 2)` 成立，
则有 `ans += C(num[i], 2) * C(num[j], 2)`
2. 若 `(j != i - j && num[j] >= 1 && num[i - j] >= 1)` 成立，
则有 `ans += C(num[i],2) * C(num[j], 1) * C(num[i - j], 1);`
一定注意随时取模。
---
## 代码 :
```cpp
//知识点：组合数，暴力
/*
By:Luckyblock
*/
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int kMaxn = 1e6 + 10;
const ll kMod = 1e9 + 7;
//=============================================================
ll n, ans, maxa, a[kMaxn], num[kMaxn];
//=============================================================
ll C(ll x, ll k) {
//求得从n个数中取出k个数的组合
//此处k=1 / 2，用了特判写法。
//k = 1 时，C(x, 1) = x;
//k = 2 时，C(x, 2) = x * (x - 1) / 2;
return (k == 1ll ? x : x * (x - 1ll) / 2ll) % kMod;
}
//=============================================================
int main() {
scanf("%lld\n", &n);
for (int i = 1; i <= n; ++ i) { //读入,并放入计数数组中
scanf("%lld", &a[i]);
maxa = max(a[i], maxa);
num[a[i]] ++;
}
for (int i = 2; i <= maxa; ++ i) { //枚举两根相等的边
if (num[i] >= 2ll) {
ll times = C(num[i], 2ll) % kMod; //求出组合数
for (int j = 1; j <= i / 2; ++ j) { //枚举被合成的边(到i / 2即可)
if (j != i - j && num[j] >= 1 && num[i - j] >= 1) //用来合成的木棒长度不等
ans += times * C(num[j], 1) * C(num[i - j], 1) % kMod;
if (j == i - j && num[j] >= 2) //用来合成的木棒长度相等
ans += times * C(num[j], 2) % kMod;
ans %= kMod;
}
}
}
printf("%lld", ans);
return 0;
}
```
恭喜妖梦获得 第16回东方Project人气投票 人妖部门第一位！