Submission #44331312

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

ll fs(ll n,ll m,ll a,ll b){
	ll res=0;
	if (a>=m){
		res+=n*(n+1)/2*(a/m),a%=m;
	}
	if (b>=m){
		res+=(n+1)*(b/m),b%=m;
	}
	ll c=(a*n+b)/m;
	if (!c){
		return res;
	}
	res+=n*c-fs(c-1,a,m,m-b-1);
	return res;
}

const int N = 2e5+5;
const ll mod = 998244353;

ll n,a[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=0; i<n; i++){
		cin>>a[i];
	}
	sort(a,a+n);
	ll s=a[0]*n,ans=(a[0]+1)%mod;
	for (int i=1; i<n; i++){
		ll l=a[i-1],r=a[i],A=n-i,B=s-l*(n-i),m=n;
		ll ad=fs(r,m,A,B)-fs(l,m,A,B)+r-l;
		(ans+=ad)%=mod,s+=(r-l)*(n-i);
	}
	cout<<ans<<endl;
	return 0;
}

// don't waste time!!!

Submission Info

Judge Result