Loading... ## Problem 有$n$根木棒,现在从中选$4$根,想要组成一个正三角形,问有几种选法? 答案对$10^9+7$取模。 <!--more--> ## Input 第一行一个整数$n$ 第二行$n$个整数,第$i$个整数$a_i$代表第$i$根木棒的长度。 ## Output 一行一个整数代表答案。 ## Samples ### Input ```txt 4 1 1 2 2 ``` ### Output ```txt 1 ``` ## Solve 取4个木棒组成正三角形,肯定有且只有一个边是由2个木棒组成的。记录每个长度的木棒的数量,由2个木棒组成边的那2个木棒的长度$i$和$j$: - 如果$i=j$:我们需要从长度为$i$的木棒中选出2个木棒作为其中一条边,然后在长度为$i+j$的木棒中选出2个作为剩余的两条边。此种情况的总数量为$C_2^{mp[i]}\times C_2^{mp[i+j]}$ - 如果$i\neq j$:三角形的边长应为$i+j$,即其中两条边是长度为$i+j$的木棒,另一条边是长度为$i$的木棒和长度为$j$的木棒拼接起来的,此种情况的总数量为$mp[i]*mp[j]*C_2^{mp[i+j]}$ <div class="tip inlineBlock info"> $mp[i]$表示长度为$i$的木棒的数量 </div> ## Code ```cpp #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ms(a,b) memset(a,b,sizeof(a)) const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; const int maxn=1e6+10; const int mod=1e9+7; const int maxm=1e3+10; using namespace std; int mp[maxn]; int C2(int n) { // cerr<<(n*(n-1)/2)%mod<<endl; return (n*(n-1)/2)%mod; } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); srand((unsigned int)time(NULL)); #endif ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; int x; int max_num=0; ms(mp,0); for(int i=0;i<n;i++) { cin>>x; mp[x]++; max_num=max(max_num,x); } int ans=0; for(int i=1;i<=max_num;i++) { for(int j=i;j<=max_num;j++) { if(i==j) ans=(ans+C2(mp[i])*C2(mp[i+j])%mod)%mod; else ans=(ans+mp[i]*mp[j]%mod*C2(mp[i+j])%mod)%mod; } } cout<<ans<<endl; #ifndef ONLINE_JUDGE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl; #endif return 0; } ``` Last modification:December 28, 2021 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏