QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488709#8815. Space Stationdalao_see_meWA 30ms8168kbC++141.7kb2024-07-24 14:25:062024-07-24 14:25:06

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 16:51:06]
  • hack成功,自动添加数据
  • (/hack/760)
  • [2024-07-24 14:25:06]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:8168kb
  • [2024-07-24 14:25:06]
  • 提交

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;
            add(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: 3884kb

input:

3 3
2 3 4

output:

499122185

result:

ok 1 number(s): "499122185"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5900kb

input:

5 1
10 20 30 40 50

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

1 9
37

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5824kb

input:

5 5
24 41 29 6 40

output:

25

result:

ok 1 number(s): "25"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3940kb

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: 30ms
memory: 8168kb

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'