QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#760#498627#8815. Space StationXiaoShanYunPanXiaoShanYunPanSuccess!2024-07-30 16:50:482024-07-30 16:50:51

Details

Extra Test:

Runtime Error

input:

100 100
1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 ...

output:


result:


IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498627#8815. Space StationXiaoShanYunPanRE 169ms49492kbC++142.8kb2024-07-30 16:50:122024-07-30 17:02:39

answer

#define allLL
using namespace std;
#include<bits/stdc++.h>
//#include<cstdio>
//#include<cstring>
//#include<string>
//#include<iostream>
//#include<utility>
//#include<algorithm>
#define MAX(x,y) (x<y?y:x)
#define MIN(x,y) (x<y?x:y)
#define ABS(x) (x<0?-x:x)
#define lb(x) ((x)&(-(x)))
#define M 17005
#define N 505
#define LL long long
#define ULL unsigned long long
#define LD long double
#ifdef allLL
#define int LL
#endif
//#define double LD
#define P 998244353
#ifdef _WIN32
#define Rand() ((rand()<<16)|rand())
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#elif _WINDOWS_
#define Rand() ((rand()<<16)|rand())
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define Rand() (rand())
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
constexpr double EPS=(1e-6);
#ifdef int
constexpr int INF=1211081101201201140;
#else
constexpr int INF=1145141919;
#endif
template<typename T>T Max(T x,T y){return MAX(x,y);}
template<typename T>T Min(T x,T y){return MIN(x,y);}
template<typename T>T Abs(T x){return ABS(x);}
template<typename T>void Swap(T&x,T&y){x^=y^=x^=y;}
template<typename T>T Gcd(T x,T y){while(y^=x^=y^=x%=y);return x;}
template<typename T1,typename T2>
T1 qp(T1 a,T2 b){T1 sum=1;
while(b){if(b&1)sum=(sum*a)%P;a=(a*a)%P;b>>=1;}return sum;}
template<typename T>
void read(T&x){
x=0;char c=getchar();/*T fl=1;*/
while(c<'0'||c>'9'){/*if(c == '-')fl=-1;*/c=getchar();}
while('/'<c&&c<':'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}/*x*=fl;*/}
template<typename T>
void write(T x){if(x<0){x=-x;putchar('-');}
if(x>9){write(x/10);}putchar(x%10|48);}
int n,m;
int a[M];
int f[M][N];
int jc[N],inv[N];
int invc(int n,int m){
	return inv[n]*jc[m]%P*jc[n-m]%P;
}
#undef int
int main(){
#ifdef allLL
#define int LL
#endif
	read(n);
	read(m);
	int sm=0;
	int mn=INF;
	for(int i=1;i<=n;i++)read(a[i]),sm+=a[i],mn=Min(mn,a[i]);
	if(mn>m){
		write(n*m);
		return 0;
	}
	jc[0]=1;
	for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%P;
	inv[n]=qp(jc[n],P-2);
	for(int i=n;i;i--)inv[i-1]=inv[i]*i%P;
	int ans=0;
	f[0][0]=1;
//	cout<<sm<<endl;
	for(int i=1;i<=n;i++)
		for(int s=sm;s>=a[i];s--)
			for(int cnt=1;cnt<=n;cnt++)
				f[s][cnt]=(f[s][cnt]+f[s-a[i]][cnt-1])%P;
	for(int cnt=1;cnt<=n;cnt++){
		for(int s=0;s<=sm;s++){
			int x=Min(s,m*cnt)*inv[cnt]%P*jc[cnt-1]%P;
			ans=(ans+x*invc(n,cnt)%P*f[s][cnt]%P)%P;
		}
	}
	write(ans);
	return 0;
#undef int
}
/*
3 3
2 3 4
*/
/*
100 100
1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 1 199 190 190 200 199 190 190 200 195 
*/