QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #489048 | #8815. Space Station | yz_ly | WA | 32ms | 11512kb | C++14 | 1.2kb | 2024-07-24 17:08:38 | 2024-07-24 17:08:39 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
inline void work(ll k){
if(k<0){
putchar('-');
k=-k;
}
if(k>9)
work(k/10);
putchar(k%10+'0');
}
/*
首先策略很简单,如果后面的平均值>m就会选择m,否则选择这次攻击
dp[i][j]表示还剩下i个数,和为j的方案数,暴力转移就行了
算期望的话用概率公式算就行了
*/
const ll mod=998244353;
int n,m;
ll dp[105][10005],ans;
ll power(ll a,ll b){
ll sum=1,k=a;
while(b){
if(b&1ll)
sum=sum*k%mod;
k=k*k%mod;
b>>=1ll;
}
return sum;
}
int main(){
n=read();
m=read();
dp[0][0]=1;
for(int i=1,x;i<=n;i++){
x=read();
for(int j=i;j;j--){
for(int k=x;k<=i*100;k++){
dp[j][k]=(dp[j][k]+dp[j-1][k-x])%mod;
}
}
}
for(int i=n;i;i--){
ll sum=0,num=0;
for(int j=i;j<=i*100;j++){
sum=(sum+dp[i][j]*min(j,m*i)%mod)%mod;
num=(num+dp[i][j])%mod;
}
ans=(ans+sum*power(num*i%mod,mod-2)%mod)%mod;
}
work(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
3 3 2 3 4
output:
499122185
result:
ok 1 number(s): "499122185"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 5 24 41 29 6 40
output:
25
result:
ok 1 number(s): "25"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
10 34 91 86 1 14 98 13 85 64 91 20
output:
707882334
result:
ok 1 number(s): "707882334"
Test #6:
score: -100
Wrong Answer
time: 32ms
memory: 11512kb
input:
100 9 83 99 170 80 174 137 1 91 111 35 69 39 148 76 142 90 105 30 114 176 196 85 26 109 162 167 171 148 169 162 159 3 4 6 33 61 163 7 77 63 8 20 13 51 26 11 149 136 134 187 96 95 113 104 128 48 167 74 18 91 200 62 167 32 5 180 189 39 63 111 68 72 81 128 42 13 57 180 111 91 83 177 34 45 158 29 114 33...
output:
993625745
result:
wrong answer 1st numbers differ - expected: '82380556', found: '993625745'