P3799 妖夢拼木棒
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??（學習自用）
提交65.01k
通過15.35k
時間限制1.00s
內存限制125.00MB
題目背景
上道題中，妖夢斬了一地的木棒，現(xiàn)在她想要將木棒拼起來。
題目描述
有?n?根木棒，現(xiàn)在從中選?44?根，想要組成一個正三角形，問有幾種選法？
答案對?109+7109+7?取模。
輸入格式
第一行一個整數?n。
第二行往下?n?行，每行?11?個整數，第?i?個整數?ai??代表第?i?根木棒的長度。
輸出格式
一行一個整數代表答案。
輸入輸出樣例
輸入 #1復制
4 1 1 2 2
輸出 #1復制
1
說明/提示
數據規(guī)模與約定
- 對于?30%30%?的數據，保證?n≤5×103。
- 對于?100%100%?的數據，保證?1≤n≤105，1≤ai?≤5×103。
#include <bits/stdc++.h> using namespace std; const int N=5e3+7; const int M=1e9+7; int num[N]; long long C(int num, int k)//組合數 { return k == 1 ? num : num * (num - 1) / 2; } int main() { int n,a,ans=0,ma=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a; ma=max(ma,a); num[a]++; } for(int i=2;i<=ma;i++) {//從2開始，因為要選四條，如果等于1不可能用四個1拼成正三角形 if(num[i]>=2) {//至少要有兩個，剩下一條邊拼起來等于這兩條邊的長 for(int j=1;j<=i/2;j++) { if(i-j==j&&num[j]>=2) ans+=C(num[i],2)*C(num[j],2)%M;//邊的總數里選兩個，拼起來等于邊的i-j邊總數選兩個 else if(i - j != j && num[j] >= 1 && num[i-j] >= 1) ans+=(C(num[i],2)*C(num[j],1))%M*C(num[i-j],1)%M; //因為沒有每次取模錯了好幾個測試點。。 } } ans%=M; } cout<<ans<<endl; return 0; }看了這位勞斯的題解：文章來源：http://www.zghlxwxcb.cn/news/detail-790105.html
-
P3799 妖夢拼木棒——枚舉+組合數學-CSDN博客
文章來源地址http://www.zghlxwxcb.cn/news/detail-790105.html
到了這里，關于P3799 妖夢拼木棒（組合數學）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
