对拍了好几组数据,发现取模的时候出现了问题。我的代码这个数据直接输出10。是哪里取模出现了问题呢?按我的理解不应该是只要可能会超的地方都因该取模吗,但这样导致了答案偏小。求大佬解答,感谢!!!
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4
//至少有两条边是一样长的。再看另外两条
#include<bits/stdc++.h>
#define int long long
using namespace std;
int maxn=0,n,ans,temp;
const int mod=1e9+7;
int b[5010],f[100010];//数据较小,可以开桶
signed main()
{
cin>>n;
f[0]=1;
for(int i=1;i<=n;i++)//预处理阶乘
{
f[i]=(f[i-1]*i)%mod;
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
maxn=max(maxn,x);
b[x]++;
}
for(int i=0;i<=maxn;i++)//直接枚举边长
{
if(b[i]<2)
continue;//不够两个直接跳过
//看自己的个数,b[i]选2
int sum=f[b[i]]/((f[2]%mod)*(f[b[i]-2]%mod)%mod);
b[i]-=2;//先用掉两个
for(int j=0;j<=i/2;j++)//枚举其中一个边长
{
if(!b[j])
continue;
int k=i-j;//另一个边长
if(!b[k])
continue;
if(j==k)
{
if(b[j]<2)
continue;
temp=f[b[j]]/((f[2]%mod)*(f[b[j]-2]%mod)%mod);
}
else temp=((b[j]%mod)*(b[k]%mod))%mod;
ans+=((sum%mod)*(temp%mod))%mod;
ans%=mod;
}
b[i]+=2;//加回来
}
cout<<ans;
return 0;
}