跳转至

P3799 妖梦拼木棒

T15:19:00+08:00 洛谷：P3799 妖梦拼木棒 - 洛谷

题意

有 \(n\) 根木棒，从中选 \(4\) 根组成正三角形，求有几种选法（答案对 \(10^9 + 7\) 取模）

思路

选 \(4\) 根，也就是说三角形的三条边分别是 \(2 + 1 + 1\)，其中一条边由两条木棒拼成，而另外两条边长度相同（用的相同一根木棒）。

首先对不同长度木棒进行计数，然后进行枚举。

先枚举三角形边长 \(i\)（要满足该长度木棒数 >= 2），再根据边长拼接一条边所使用的木棒 \(j\) 和 \(i - j\)，这里会产生两种情况：

  • 若 \(i = i - j\)，那么拼成此正边长三角形的方案数即为 \(C_{cnt_i}^2 \cdot C_{cnt_j}^2\)
  • 若 \(i \neq i - j\)，那么拼成此边长正三角形的方案数为 \(C_{cnt_i}^2 \cdot cnt_j \cdot cnt_{i - j}\)

最后再累加起来，即为总的方案数。 记得随着计算取模。

码

C++
 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
38
39
40
41
#include <iostream>

#define ll long long

using namespace std;

const int MAXA = 5E3;
const int MOD =  1E9 + 7;

int cnt[MAXA];

ll cn2(ll n) {
    return n * (n-1) / 2;
}

int main() {
    int n; cin >> n;

    int maxa = 0;
    for (int i = 1, a; i <= n; i++) {
        cin >> a;
        maxa = max(maxa, a);
        cnt[a]++;
    }

    ll ans = 0;
    for (int i = 2; i <= maxa; i++) {
        if (cnt[i] >= 2) {
            for (int j = 1; j<<1 <= i; j++) {
                if (j == i-j && cnt[j] >= 2) {
                    ans = (ans + ((cn2(cnt[j]) % MOD) * (cn2(cnt[i]) % MOD)) % MOD) % MOD;
                } else if (j != i-j && cnt[j] && cnt[i-j]) {
                    ans = (ans + (((cnt[j] * cnt[i-j]) % MOD) * (cn2(cnt[i]) % MOD)) % MOD) % MOD;
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

评论