QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488890 | #8815. Space Station | white_ice | WA | 49ms | 9716kb | C++17 | 1.2kb | 2024-07-24 16:06:24 | 2024-07-24 16:06:25 |
Judging History
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'