QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488708 | #8815. Space Station | dalao_see_me | WA | 29ms | 8092kb | C++14 | 1.7kb | 2024-07-24 14:23:39 | 2024-07-24 14:23:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
return x * f;
}
int quickpow(int a, int b, int mod) {
int res = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod)
if (b & 1) res = 1LL * res * a % mod;
return res;
}
const int N = 105, mod = 998244353;
int f[N][N * N], a[N], fac[N], Inv[N], inv[N * N];
int n, m, V = 100, ans;
int C(int a, int b) {
if (a < 0 || b < 0 || a < b) return 0;
return 1LL * fac[a] * Inv[b] % mod * Inv[a - b] % mod;
}
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
void Solve() {
n = read(); m = read(); fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
Inv[n] = quickpow(fac[n], mod - 2, mod);
for (int i = n - 1; ~i; i--) Inv[i] = 1LL * Inv[i + 1] * (i + 1) % mod;
for (int i = 1; i <= n * V; i++) inv[i] = quickpow(i, mod - 2, mod);
for (int i = 1; i <= n; i++) a[i] = read();
f[0][0] = 1;
for (int i = 1; i <= n; i++) for (int j = i; j; j--)
for (int k = a[i]; k <= i * V; k++) add(f[j][k], f[j - 1][k - a[i]]);
for (int i = 1; i <= n; i++) {
int p = quickpow(C(n, i), mod - 2, mod), t;
for (int j = 0; j <= n * V; j++) {
if (j <= i * m) t = 1LL * j * inv[i] % mod; else t = m;
ans = (ans + 1LL * p * f[i][j] % mod * t) % mod;
}
}
printf("%d\n", ans);
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int _ = 1;
while (_--) Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
3 3 2 3 4
output:
499122185
result:
ok 1 number(s): "499122185"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
5 5 24 41 29 6 40
output:
25
result:
ok 1 number(s): "25"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3888kb
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: 29ms
memory: 8092kb
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:
535753803
result:
wrong answer 1st numbers differ - expected: '82380556', found: '535753803'