n^2logn求赞
查看原帖
n^2logn求赞
242524
JRzyh楼主2020/7/26 18:20

部分分也拿不到

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull dp[200008][5];
ull ShowDown(ull m,ull n)
{
	if(dp[m][n]!=0) return dp[m][n]%998244353;
	if(m==n||n==0||m==1||m==0)dp[m][n]=1;
	else if(n==1) dp[m][n]=m%998244353;  
	else dp[m][n]=ShowDown(m-1,n)%998244353+ShowDown(m-1,n-1)%998244353;
	return dp[m][n]%998244353;
}
ull C(ull m,ull n)
{
  	return ShowDown(m,min(m,m-n))%998244353;
}
int n,a,ans;
map<int,int>mp;
vector<int>l;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		if(mp[a]==0)l.push_back(a);
		mp[a]++;
	}
	if(l.size()==1)
	{
		cout<<C(n,3);
		return 0;
	}
	//sort(l.begin(),l.end());
	for(int i=0;i<l.size();i++)
	{
		for(int j=i+1;j<l.size();j++)
		{
			if(l[i]*2>l[j])
			{
				ans+=mp[l[j]]-1;
				ans%=998244353;
			}
			if(l[j]*2>l[i])
			{
				ans+=mp[l[i]]-1;
				ans%=998244353;
			}
		}
	}
	cout<<ans;
	return 0;
}

2020/7/26 18:20
加载中...