当然这是我第一次写博客,我在我自己的笔记上面不知道写多少注释加理解了,一直苦于找不到博客;
蒟蒻第一次开始系统性的刷题,没想到第二道就遇到了排列组合的数学题,可恶啊,还是被一个六年级的小学生教会的;
# 妖梦拼木棒,P3799 妖梦拼木棒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
## 题目背景
上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。
## 题目描述
有 n根木棒，现在从中选 4 根，想要组成一个正三角形，问有几种选法？
答案对 10^9+7取模。
## 输入格式
第一行一个整数 n。
第二行往下 n 行，每行 1个整数，第 i个整数 a_i 代表第 i 根木棒的长度。
## 输出格式
一行一个整数代表答案。
## 样例 #1
### 样例输入 #1
```
4
1
1
2
2
```
### 样例输出 #1
```
1
```
接下来上代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100010; 4 int n,a[N],res; 5 int main() 6 { 7 cin>>n; 8 for(int i=0;i<n;i++) cin>>a[i]; 9 10 return 0; 11 } 12 #include<bits/stdc++.h> 13 #define ll long long//定义long long 减少码量 14 using namespace std; 15 const ll N=1e6+10,mod=1e9+7; 16 ll n,ans,maxx=-1,minn=0x3f3f,num[N];//num数组记录长度为a的木棍的数量; 17 int main() 18 { 19 cin>>n; 20 for(int i=1;i<=n;i++) 21 { 22 ll a; 23 cin>>a,num[a]++; 24 maxx=max(maxx,a);//找出长度的最大值和最小值 25 minn=min(minn,a); 26 } 27 for(int i=minn+1;i<=maxx;i++)//开始从最小+1遍历,为什么不是minn? 28 //因为如果是minn的话,是不可能用4个木棍拼接成功的,相同长度的木棍只能用3个拼接 29 { 30 if(num[i]>=2)//如果相同长度的木棍超过两个了,说明接下来的两个其他长度的木棍就有可能形成一次拼接 31 { 32 for(int j=minn;j<=i/2;j++)//防止重复计算,就从i/2结束了; 33 { 34 //接下来的是重要代码,考察小学(高中)知识,排列组合从n个里面选2个和从n个里面选1个都是可以自己推导出公式的 35 //因为选的数量很小,很好推,如果是1个,那就是n,如果是取两个,那就是(1/2*n*n-1),自己参考高中排列组合; 36 if(j!=i-j) ans+=num[i]*(num[i]-1)*num[j]*num[i-j]/2,ans%=mod; 37 //如果这两个木棍长度不一样,那么就是从j长度的木棍中取一个,从i-j的长度中取一个; 38 else if(num[j]>=2&&2*j==i) ans+=num[i]*(num[i]-1)*num[i/2]*(num[i/2]-1)/4,ans%=mod; 39 //如果长度一样,先判断这个长度木棍是否够两个,然后再取,注意每次都要取模 40 } 41 } 42 } 43 cout<<ans; 44 }