题解 P3799 【妖梦拼木棒】

· · 题解

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

原题面

\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人气投票 人妖部门第一位！