QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489411#8815. Space Station_log_WA 57ms28752kbC++171.2kb2024-07-24 20:00:562024-07-24 20:00:56

Judging History

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

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

answer

# include <bits/stdc++.h>
# define mod 998244353
# define int long long
# define rep(i, j, k) for(int i = j; i <= k; ++i)
using namespace std;

int n, m, ans, c;
int a[105], preSum[105], fac[105], inv1, inv[105];
int dp[2][105][100 * 200 + 5];

inline int qp(int a, int b) {int mul = 1; while(b) {if(b & 1) mul = mul * a % mod; a = a * a % mod, b >>= 1;} return mul;}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m; rep(i, 1, n) cin >> a[i], preSum[i] = preSum[i - 1] + a[i];
    dp[0][0][0] = fac[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod; inv1 = qp(fac[n], mod - 2);
    rep(i, 1, n) inv[i] = qp(i, mod - 2);
    rep(i, 1, n) rep(j, 0, i) rep(k, 0, 200 * j)
        if(j && k >= a[i]) dp[i & 1][j][k] = (dp[(i & 1) ^ 1][j][k] + dp[(i & 1) ^ 1][j - 1][k - a[i]]) % mod;
        else dp[i & 1][j][k] = dp[(i & 1) ^ 1][j][k];
    rep(j, 1, n) rep(k, 1, preSum[n]) {
        if(!dp[n & 1][j][k]) continue;
        if(j * m >= k) c = k * inv[j] % mod;
        else c = m;
        ans = (ans + dp[n & 1][j][k] * fac[j] * fac[n - j] % mod * c % mod * inv1) % mod;
    }
    cout << ans << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5616kb

input:

3 3
2 3 4

output:

499122185

result:

ok 1 number(s): "499122185"

Test #2:

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

input:

5 1
10 20 30 40 50

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

1 9
37

output:

9

result:

ok 1 number(s): "9"

Test #4:

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

input:

5 5
24 41 29 6 40

output:

25

result:

ok 1 number(s): "25"

Test #5:

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

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: 57ms
memory: 28752kb

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:

521392380

result:

wrong answer 1st numbers differ - expected: '82380556', found: '521392380'