题解 P3799 【妖梦拼木棒】
Terrible
·
·
题解
这道题纯暴力是不行的，需要结合组合数学求解。
思路：
4根木棒组合成正三角形，那么一定是2个小木棒组成其中一边，另外两边是两个相等的大木棒。
把2个小木棒看成一个整体，和大木棒进行组合数求解即可。
首先
我们需要两个桶：x[i]表示用2个小木棒（小是相对的）组合成长度为i的整体组合种类数，y[i]表示长度为i的木棒数目。
然后
题目会给出y[i]，怎么求x[i]呢？
举个例子：x[4]=y[1]*y[3]+C_{y[2]}^2，其中(y[2]\geq 2)。
从长度为1的木棍中抽出一个，从长度为3的木棍中抽出一个，就可以组成长度为4的木棍，根据乘法原理相乘即可，然后加上从长度为2的木棍中抽出两个的种类数。
·两个**不同**木棍组合，$x[i+j]$+=$y[i]*y[j]$。其中$i<j$，避免重复计数；
·两个**等长**木棍组合,$x[2*i]$+=$C_{y[i]}^2$。其中$(y[i]\geq 2)$。
#### 最后
那么长度为$i$时，组合数即：从长度为$i$的木棍中抽出两个的种类数乘以$x[i]$，也就是$sum_i=C_{y[i]}^2*x[i]=\frac{y[i]*(y[i]-1)}{2}*x[i]$，其中$(y[i]\geq 2)$。
**枚举**长度$i$，计数得出结果。（**记得取模！**）
## 代码：
```cpp
#include<cstdio>
inline short read()//快读
{
register short a=0;register char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')a=a*10+(c^48),c=getchar();
return a;
}
int x[5001],y[5001];
//x[i]表示两根小棍子总长度为i的组合数目
//y[i]表示一根棍子长度为i的数目
//两根棍子组合长度超过5000不需要记录
int main()
{
int n;register int i,j,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)y[read()]++;
//将棍子长度的数据装入桶里
for(i=1;i<=2500;i++)
for(j=i+1;j<=5000-i;j++)
x[i+j]+=y[i]*y[j];
//计算两个不等木棍的组合数目
for(i=1;i<=2500;i++)
if(y[i]>1)
x[2*i]+=y[i]*(y[i]-1)/2;
//加上两个等长木棍的组合数目
for(i=1;i<=5000;i++)
if(y[i]>1)
sum+=y[i]*(y[i]-1)/2*x[i],sum%=1000000007;
//求组合数，sum=y*(y-1)/2*x，还要记得取模！
printf("%d",sum);
}
//PS：吸氧跑得还可以，100+ms
```