QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488892#8815. Space Stationc20150005WA 0ms3912kbC++141.1kb2024-07-24 16:06:452024-07-24 16:06:46

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 16:51:06]
  • hack成功,自动添加数据
  • (/hack/760)
  • [2024-07-24 16:06:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3912kb
  • [2024-07-24 16:06:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){int f=1;while(!isdigit(c))f=(c^'-'?1:-1),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=214;const ll mod=998244353;
ll fac[N],inv[N];
ll ksm(ll a,ll b,ll r=1){while(b){if(b&1)r=r*a%mod;a=a*a%mod;b>>=1;}return r;}
void init(int n){
    inv[0]=fac[0]=inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod,inv[i]=inv[i-1]*inv[i]%mod;
}
ll C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int n,m;
int a[N],S;
int dp[N][N*N];
int md(const int&x){return x>=mod?x-mod:x;} 
int main(){
	n=rd(),m=rd();
	init(n);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		S+=(a[i]=rd());
		for(int j=i;j>=1;j--)for(int k=S;k>=a[i];k--)
		dp[j][k]=md(dp[j][k]+dp[j-1][k-a[i]]);
	}
	ll ans=0;
	for(int i=1;i<=n;i++)for(int j=1,X=ksm(C(n,i),mod-2);j<=S;j++){
		if(i*m<j)ans=(ans+X*m%mod*dp[i][j])%mod;
		else ans=(ans+X*j%mod*ksm(i,mod-2)%mod*dp[i][j])%mod;
	}printf("%lld",ans);
	return 0;
}
/*
3 3
2 3 4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

input:

3 3
2 3 4

output:

499122185

result:

ok 1 number(s): "499122185"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

5 1
10 20 30 40 50

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

1 9
37

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3912kb

input:

5 5
24 41 29 6 40

output:

-25165756

result:

wrong answer 1st numbers differ - expected: '25', found: '-25165756'