QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488763 | #8815. Space Station | lefy | WA | 0ms | 3820kb | C++14 | 1.2kb | 2024-07-24 15:12:34 | 2024-07-24 15:12:38 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110,mod=99824353;
ll inv[N*N<<1],f[N][N*N<<1],fac[N],Inv[N];
int a[N];
ll pw(ll x,int cnt){
ll ans=1;
while(cnt){
if(cnt&1)ans=ans*x%mod;
x=x*x%mod;
cnt>>=1;
}
return ans;
}
ll C(int x,int y){
return fac[x]*Inv[y]%mod*Inv[x-y]%mod;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int sum=0;fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
Inv[n]=pw(fac[n],mod-2);
for(int i=n-1;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
inv[1]=1;
for(int i=2;i<=n*200;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j;j--)for(int k=i*200;k>=a[i];k--){
f[j][k]+=f[j-1][k-a[i]];
f[j][k]%=mod;
}
}
ll ans=0;
for(int i=1;i<=n;i++){
ll cnt=pw(C(n,i),mod-2);
for(int j=1;j<=n*200;j++){
if(j<=i*m)ans+=f[i][j]*cnt%mod*j%mod*inv[i]%mod;
else ans+=f[i][j]*cnt%mod*m%mod;
ans%=mod;
}
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3820kb
input:
3 3 2 3 4
output:
49912185
result:
wrong answer 1st numbers differ - expected: '499122185', found: '49912185'