1349D - Slime and Biscuits - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define se second
#define lhx make_pair
#define eb emplace_back
#define rep(i,l,r) for(int i=(l); i<=(r); ++i)
#define rep_(i,l,r) for(int i=(l); i>=(r); --i)
typedef long long lr;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
constexpr int N=500500,mod0=1e9+7,mod1=998244353,mod2=1004535809,mod3=2013265921;
constexpr db pi=acos(-1.0),eps=1e-9;
constexpr int inf32=0x3f3f3f3f,Inf32=0xcfcfcfcf;
constexpr lr inf64=0x3f3f3f3f3f3f3f3f,Inf64=0xcfcfcfcfcfcfcfcf;
template<typename T>il T Max(T x,T y)
{
    return (x>y)? x:y;
}
template<typename T>il T Min(T x,T y)
{
    return (x<y)? x:y;
}
template<typename T>il T gcd(T x,T y)
{
    return (!y)? x:gcd(y,x%y);
}
template<typename T>il T Abs(T x)
{
    return (x>0)? x:(-x);
}
int n,m,a[N],f[N];
pii g[N];
il int Inv(int x)
{
	int y=mod1-2,mul=1;
	while(y)
	{
		if(y&1)
			mul=(lr)mul*x%mod1;
		x=(lr)x*x%mod1,y>>=1;
	}
	return mul;
}
il void Solve()
{
    cin>>n;
    rep(i,1,n)
		cin>>a[i],m+=a[i];
	rep(i,0,m-1)
	{
		int p=Inv(((lr)(n-2)*i%mod1+m-(lr)(n-1)*i%mod1*g[i-1].fi%mod1+mod1)%mod1);
		g[i].fi=(lr)(m-i)*p%mod1,g[i].se=((lr)(n-1)*i%mod1*g[i-1].se%mod1+(lr)(n-1)*m%mod1)%mod1*p%mod1;
	}
	rep_(i,m-1,0)
		f[i]=((lr)f[i+1]*g[i].fi%mod1+g[i].se)%mod1;
	int ans=0;
	rep(i,1,n)
		ans=(ans+f[a[i]])%mod1;
	ans=(ans-(lr)(n-1)*f[0]%mod1+mod1)%mod1;
	cout<<(lr)ans*Inv(n)%mod1<<'\n'; 
}
int main()
{
#ifdef FILEIO
    string pre="hack",isuf="in",osuf="out";
    freopen((pre+"."+isuf).c_str(),"r",stdin);
    freopen((pre+"."+osuf).c_str(),"w",stdout);
#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    while(T--)
        Solve();
    return 0;
}