求助40分
查看原帖
求助40分
90027
fanypcd楼主2020/10/3 20:33

Sub#3#4全对,#1#2各第一点错误,求教大佬还有什么特殊情况吗

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	const long long mod = 998244353;
	long long n, t[200005], a[200005], l, r, ans = 0;
	memset(t, 0, sizeof(t));
	cin >> n;
	for(long long i = 1; i <= n; i++)
	{
		cin >> a[i];
		t[a[i]]++;
	}
	for(long long i = 1; i <= 200005; i++)
	{
		t[i] += t[i - 1];
		t[i] %= mod;
	}
	sort(a + 1, a + n + 1);
	long long last = 0;
	for(long long i = 1; i <= n; i++)
	{
		long long tt = t[a[i]] - t[a[i] - 1];
		tt %= mod;
		if(a[i] == last)
		{
			continue;
		}
		if(tt < 2)
		{
			continue;
		}
		last = a[i];
		l = lower_bound(a + 1, a + n + 1, 0) - a + 1;
		r = lower_bound(a + 1, a + n + 1, 2 * a[i]) - a - 1;
		ans += ((tt * (tt - 1) / 2 % mod) * ((t[a[r]] - t[a[l] - 1] - tt) % mod)) % mod;
		ans %= mod;
		if(tt >= 3)
		{
			ans += ((tt * (tt - 1) * (tt - 2)) / 6) % mod;
			ans %= mod;
		}
	}
	cout << ans;
	return 0;
}
2020/10/3 20:33
加载中...