题解 P3799 【妖梦拼木棒】

灵乌路空

2019-07-09 17:52:05

Solution

知识点:组合数学,暴力枚举 [原题面](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人气投票 人妖部门第一位!