QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #488781 | #8815. Space Station | aqz180321 | WA | 1ms | 3712kb | C++14 | 1.1kb | 2024-07-24 15:17:59 | 2024-07-24 15:17:59 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <cstdio>
typedef long long ll;
const ll mod = 998244353;
const ll N = 110;
const ll A = 210;
ll n, m, ans, sum;
ll a[N], C[N][N], f[N][N * A];
ll quickly_pow (ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = ans * base % mod;
base = base * base % mod;
b >>= 1;
}
return ans;
}
ll inv (ll x) {
return quickly_pow (x, mod - 2);
}
int main() {
std::cin >> n >> m;
for (ll i = 1; i <= n; i++)
std::cin >> a[i];
for (ll i = 0; i <= n; i++) {
C[i][0] = 1;
for (ll j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
f[0][0] = 1;
for (ll i = 1; i <= n; i++) {
sum = sum + a[i];
for (ll j = i; j >= 1; j--)
for (ll k = sum; k >= a[i]; k--)
f[j][k] = (f[j][k] + f[j - 1][k - a[i]]) % mod;
}
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= sum; j++) {
ll now = inv(C[n][i]) * f[i][j] % mod;
if (j >= i * m) now = now * m % mod;
else now = now * inv(i) * j % mod;
ans = (ans + now) % mod;
}
std::cout << 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: 3700kb
input:
3 3 2 3 4
output:
499122185
result:
ok 1 number(s): "499122185"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
5 5 24 41 29 6 40
output:
25
result:
ok 1 number(s): "25"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
10 34 91 86 1 14 98 13 85 64 91 20
output:
763359361
result:
wrong answer 1st numbers differ - expected: '707882334', found: '763359361'