关于过程中取模的问题,急!
查看原帖
关于过程中取模的问题,急!
250699
mot1ve楼主2020/11/12 19:53

对拍了好几组数据,发现取模的时候出现了问题。我的代码这个数据直接输出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;
}
2020/11/12 19:53
加载中...