QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488890#8815. Space Stationwhite_iceWA 49ms9716kbC++171.2kb2024-07-24 16:06:242024-07-24 16:06:25

Judging History

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

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

answer

//2024.7.24
//by white_ice
//# 8815. Space Station
#include<bits/stdc++.h>
using namespace std;
#define itn long long 
#define int long long
constexpr int oo = 102;
constexpr int op = 10004;
constexpr int mod = 998244353;

itn ngm(itn a,itn b){return a<b?a:b;}

itn n,m;
itn c[oo],ic[oo];

__inline int qpow(itn a,itn b){int out=1;while(b){if(b&1)(out*=a)%=mod;b>>=1;(a*=a)%=mod;}return out;}

__inline void getc(itn n){
    0[c] = 1;for (itn i=1;i<=n;++i)i[c]=(i-1)[c]*i%mod;
    n[ic]=qpow(n[c],mod-2);
    for (itn i=n;i>=2;--i)(i-1)[ic]=i[c]*i%mod;
//    cout << n[c];
}

int f[oo][op];
int out;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> m ;
    getc(n);
    f[0][0] = 1;
    for (itn x,i=1;i<=n;++i){
        cin >> x;
        for (int j=i;j>=1;--j){//01背包,倒序
            for (int k=0;k<=(j-1)*200;++k){
                (f[j][k+x] += f[j-1][k])%=mod;
            }
        }
    }
    for (int i=1;i<=n;++i){
        itn cur = 0;
        for (int j=1;j<=i*200;++j){
            (cur+=ngm(i*m,j)*f[i][j])%=mod;
        }
        (out+=cur*ic[n]%mod*c[i-1]%mod*c[n-i]%mod)%=mod;
    }
    
    cout << out;
    return 0;
}   



详细

Test #1:

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

input:

3 3
2 3 4

output:

499122185

result:

ok 1 number(s): "499122185"

Test #2:

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

input:

5 1
10 20 30 40 50

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

1 9
37

output:

9

result:

ok 1 number(s): "9"

Test #4:

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

input:

5 5
24 41 29 6 40

output:

25

result:

ok 1 number(s): "25"

Test #5:

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

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: 49ms
memory: 9716kb

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:

522650078

result:

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