Submission #39387035

---

Source Code Expand

#include<cstdio>
#include<cctype>
#include<map>
#include<vector>
#include<algorithm>

#define maxn 5555

const int mod=998244353;

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r*10)+(c^48),c=getchar();
	return f?-r:r;
}

inline long long qpow(long long a,int b){
	long long ans=1;
	for(;b;b>>=1){
		if(b&1)(ans*=a)%=mod;
		(a*=a)%=mod;
	}
	return ans;
}

int n,cnt[maxn];

long long f[maxn],p[maxn][maxn];

long long pw[maxn],frac[maxn],invf[maxn];

inline long long C(int n,int m){
	if(n<m||m<0)return 0;
	return frac[n]*invf[m]%mod*invf[n-m]%mod;
}

int main(){
	n=read<int>();
	for(int i=1;i<=n;i++)
		cnt[read<int>()]++;
	frac[0]=1;
	for(int i=1;i<=n;i++)
		frac[i]=frac[i-1]*i%mod;
	invf[n]=qpow(frac[n],mod-2);
	for(int i=n;i;i--)
		invf[i-1]=invf[i]*i%mod;
	pw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=pw[i-1]*2%mod;
	long long Inv=qpow(pw[n],mod-2),invn=qpow(n,mod-2);
	for(int x=0;x<n;x++)
		for(int y=0;y<=x+1;y++){
			long long s=C(x,x-y);
			(p[x][y]+=pw[n-x]*(n+1)%mod*s)%=mod;
			(p[x][y]+=(pw[n-x]*(x-y+1)+pw[n-x-1]*(n-x))%mod*(C(x,x-y+1)+mod-s))%=mod;
			(p[x][y]*=Inv*invn%mod)%=mod;
		}
	for(int i=0;i<n;i++){
		f[i+1]=f[i]+mod-invn;
		for(int j=0;j<=i;j++)
			(f[i+1]+=(mod-p[i][j])*f[j])%=mod;
		(f[i+1]*=qpow(p[i][i+1],mod-2))%=mod;
	}
	long long ans=mod-f[n];
	for(int i=1;i<=n;i++)
		ans+=f[cnt[i]];
	printf("%lld\n",ans%mod);
	return 0;
}

Submission Info

Judge Result