先是错误的代码,求大佬解惑
int main(void)
{
int bucket[5050]={0, };
long long int ans=0, tmp;
int i, j, n, max=-99999999;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &j);
if (max < j)
max = j;
bucket[j]++;
}
//枚举可能的边长
for (i = 1; i <= max; i++)
{
//最长边至少需要两根
if (bucket[i] < 2)
continue;
//对最长边的选择方案数
//C(bucket[i], 2)
tmp = bucket[i] * (bucket[i] - 1) / 2;
//枚举需要拼接的两根火柴中较小的那根,(保证它是较小的)防止重复枚举
//到i/2即可,例如2+5=7,5+2=7
for (j = 1; j*2 <= i; j++)
{
//特殊处理i为偶数导致的3+3=6这样的拼接
if (j*2 == i && bucket[j] >= 2)
tmp *= bucket[j]*(bucket[j]-1) / 2;
else if (bucket[j]*bucket[i-j] != 0)
//C(bucket[j], 1)*C(bucket[i-j], 1)
tmp *= bucket[j]*bucket[i-j];
tmp = tmp * (bucket[i] * (bucket[i] - 1)) / 2;
ans = (ans + tmp) % 1000000007;
}
}
printf("%lld", ans % 1000000007);
return 0;
}
下面是改过后的代码,是对的:
int main(void)
{
int bucket[5050]={0, };
long long int ans=0, tmp;
int i, j, n, max=-99999999;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &j);
if (max < j)
max = j;
bucket[j]++;
}
//枚举可能的边长
for (i = 1; i <= max; i++)
{
//枚举需要拼接的两根火柴中较小的那根,(保证它是较小的)防止重复枚举
//到i/2即可,例如2+5=7,5+2=7
for (j = 1; j <= i / 2; j++)
{
//特殊处理i为偶数导致的3+3=6这样的拼接
if (j*2 == i)
tmp = bucket[j]*(bucket[j]-1)/2;
else
//C(bucket[j], 1)*C(bucket[i-j], 1)
tmp = (bucket[j]*bucket[i-j]);
ans = (ans + tmp * (bucket[i] * (bucket[i] - 1)) / 2) % 1000000007;
}
}
printf("%lld", ans);
return 0;
}