当前位置： 移动技术网 > 移动技术>移动开发>IOS > luogu 6686 混凝土数学

luogu 6686 混凝土数学

2020年08月10日  | 移动技术网移动技术  | 我要评论

题目

这题比较有意思，记录一下。难的地方在于要理清思路。

首先如果某一条边出现次数>=3，那么它任意三条边都可以作为答案，然后就是，当一条边出现次数>=2时，它才可以作为三角形的腰，然后二分去找能跟这个腰组成三角形的边，前缀和优化一下计数方式，然后就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map> 
#include<string>
#include<queue>
#include<stack> 
#include<bitset>
#include<list>
#define IO ios::sync_with_stdio(false)
#define int long long
using namespace std;
const int mod=998244353;
int c[200005][6],cnt[200005],a[200005],sum[200005],n;
int C(int x,int y)
{
	if(x<y)return 0;
	else return c[x][y];
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		cnt[a[i]]++;
	}
	c[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		c[i][0]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=4;j++)
		{
			c[i][j]=(c[i-1][j-1]%mod+c[i-1][j]%mod)%mod;
		}
	}
	sort(a+1,a+n+1);
	int len=unique(a+1,a+n+1)-(a+1);
	for(int i=1;i<=len;i++)
	{
		sum[i]=sum[i-1]+cnt[a[i]];
	}
	int ans=0;
	for(int i=1;i<=len;i++)
	{
		ans=(ans%mod+C(cnt[a[i]],3)%mod)%mod;
		int j=lower_bound(a+1,a+len+1,2*a[i])-a;
		ans=(ans%mod+(C(cnt[a[i]],2)%mod*(sum[j-1]-cnt[a[i]])%mod)%mod)%mod;
	}
	cout<<ans;
}

本文地址：https://blog.csdn.net/qq_37073764/article/details/107877094

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网