題目背景
上道題中，小 Y 斬了一地的木棒，現在她想要將木棒拼起來。
題目描述
有?n?根木棒，現在從中選?4?根，想要組成一個正三角形，問有幾種選法？
答案對?109+7?取模。
輸入格式
第一行一個整數?n。
第二行往下?n?行，每行?1?個整數，第?i?個整數?ai??代表第?i?根木棒的長度。
輸出格式
一行一個整數代表答案。
輸入輸出樣例
輸入 #1復制
4 1 1 2 2
輸出 #1復制
1
說明/提示
數據規模與約定
- 對于?30%?的數據，保證?n≤5×103。
- 對于?100%?的數據，保證?1≤n≤105，1≤ai?≤5×103
????????卡了好長時間終于AC了嗚嗚嗚。
題目分析
? ? ? ? 這道題不能使用dfs枚舉每一種情況會超時，別問我怎么知道的。
????????改變思路，我們側重于題目本身進行分析。要想利用4個木棒得到一個正三角形，首先得有兩個相同的木棒，并且這個長度的木棒會比另外兩個木棒的長度長。我們合理使用數組來存儲每個長度木棒的數量，將數組a開到滿足題目的最大值。
? ? ? ? 從大到小進行遍歷，如果它的值a[i]大于等于2，則在1到i/2的范圍內尋找滿足題目情況的值。
????????這里使用到的還是重要的組合公式。兩種物品分別有m和n個，每種里面都選擇一種，則有m * n種組合。
這里給出一種關于沒有順序的cnm的計算代碼(邊乘邊除法)：
ll C(ll n, ll m) {ll ans = 1;for (ll i = 1; i <= m; i++) {ans = ans * (n - m + i) / i;}return ans;
}對于m == 2的情況我們直接可以返回n * (n - 1) / 2;
代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
int n, a[5005] = {0};int zuhe(int m){if (m < 2) return 0;return (ll)m * (m - 1) / 2 % mod;;
}
int main()
{ll sum = 0;cin >> n;int tmp;for (int i = 0; i < n; i++){cin >> tmp;a[tmp]++;}for(int i = 5001; i > 1; i--){if(a[i] <= 1)continue;else{// >= 2int cm2 = zuhe(a[i]);for(int j = 1; j <= i / 2; j++){//找匹配的數子if(j != i - j){if(a[j] > 0 && a[i - j] > 0){//可以相加的兩個數都是大于0的sum += a[j] * a[i - j] * cm2 % mod;sum %= mod;}}else{// j == i - jif(a[j] > 1)sum += zuhe(a[j]) * cm2 % mod;sum %= mod;}}}sum %= mod;}cout << sum%mod;
}
