QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488814 | #8815. Space Station | zhao_daodao | WA | 1ms | 3764kb | C++14 | 1.2kb | 2024-07-24 15:29:52 | 2024-07-24 15:29:53 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=200+5;
const int mod=998244353;
inline int ksm(int a, int b){
int cnt = 1;
while(b) {
if(b & 1) cnt = cnt * a % mod;
a = a * a % mod; b >>= 1;
}return cnt;
}
int n,m,a[MAXN];
int dp[MAXN][MAXN];
int fac[MAXN],inv[MAXN];
signed main(){
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;int all = 0;
for(int i = 1; i <= n; i++)cin >> a[i], all += a[i];
fac[0] = 1;
for(int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
inv[n] = ksm(fac[n], mod - 2);
for(int i = n - 1; i >= 0; i--)
inv[i] = inv[i + 1] * (i + 1) % mod;
function <int(int, int)> C = [&](int a, int b) -> int{return fac[a] * inv[b] % mod * inv[a - b] % mod;};
dp[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = i; j >= 1; j--)
for(int k = all; k >= a[i]; k--)
(dp[j][k] += dp[j - 1][k - a[i]]) %= mod;
int ans = 0;
for(int i = 1; i <= n; i++){
int sum = 0;
for(int j = 1; j <= all; j++){
if(i * m > j)(sum += dp[i][j] * j % mod * ksm(i, mod - 2) % mod) %= mod;
else (sum += dp[i][j] * m % mod) %= mod;
}
(ans += sum * ksm( C(n, i), mod - 2) % mod) %= mod;
}
cout << ans << "\n";
}
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: 3628kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 5 24 41 29 6 40
output:
25
result:
ok 1 number(s): "25"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3624kb
input:
10 34 91 86 1 14 98 13 85 64 91 20
output:
905306424
result:
wrong answer 1st numbers differ - expected: '707882334', found: '905306424'