自动搬运

查看原文

来自洛谷，原作者为

	灵乌路空 已退役 | 东方众OIer交流群 (幻想乡养老院) : 691090556

搬运于2025-08-24 21:52:49，当前版本为作者最后更新于2019-07-09 17:52:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

知识点:组合数学，暴力枚举

原题面

$\text{Rewrited on 2020.6.14.}$
感谢 TheStars 发现错误，并提出宝贵意见。

题目要求

有 $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);

一定注意随时取模。

代码 :

//知识点：组合数，暴力
/*
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人气投票 人妖部门第一位！