P3799 妖梦拼木棒——枚举+组合数学

妖梦拼木棒

题目背景

上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。

题目描述

有 $n$ 根木棒，现在从中选 $4$ 根，想要组成一个正三角形，问有几种选法？

答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

第二行往下 $n$ 行，每行 $1$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 根木棒的长度。

输出格式

一行一个整数代表答案。

样例 #1

样例输入 #1

4 
1
1
2
2
1
2
3
4
5

样例输出 #1

1
1

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\le 5\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le a_i\le 5\times 10^3$。

分析

1. 首先此题可以发现，当拼出的木棒满足等边三角形时，那么有两根是相同的，另外较短的两根之和要等于前面的那两根。假设两根较短的边长为a,b，两根一样长的为c，有等式a+b=c；
2. 枚举a,b（那么c就是a+b，不用枚举），然后判断每种情况下，满足等式的方案数，这里就需要组合的知识，见下图，看看，在长度等于a中的所有木棒选出来1根有几种方案，在长度等于b中的所有木棒中选出一根有多少中方案，在长度等于a+b的所有木棒中选出两根有多少方案，，乘一块累加在ans即可，组合的计算，用一个C2函数实现；
3. 由于要避免方案的重复比如，a=1,b=2和a=2,b=1，会被重复计算方案数，所以我们让a<=b，即可解决重复问题；
4. 其次我们要分两种情况a=b和a!=b，因为他们是两堆中各选一个、一堆中选两个，效果不同；
5. 关于每个数出现几次，也就是为了后面从某一堆中选元素的方案数，用一个桶cnt预处理了；
6. 刚开始cnt数组开的5005，提交RE了，感觉题目给的数据范围不太对，题目说a[i]最大5*10^3,数组开5005RE了，多加个0，就A了；以及在求余处理，每计算一步（两数相乘后），都要取余一下，避免极端情况；

#include

using namespace std;

const int Mod = 1e+9 + 7;
int n, ans;
int a[100005];
int cnt[50005];//桶

//求C(k,2)，k个数中选2个
int C2(int k) {
    return (k * (k - 1) % Mod) / 2;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    //a+b=c
    //枚举两个短边
    for (int i = 1; i <= 5000; i++) {//a
        for (int j = i; j <= 5000; j++) {//b
            if (i == j) {//a=b
                ans = (ans + (C2(cnt[i + j]) * C2(cnt[i])) % Mod) % Mod;
            } else {
                ans = (ans + (C2(cnt[i + j]) * (cnt[i] * cnt[j]) % Mod) % Mod) % Mod;
            }
        }
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37