QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#453981 | #8815. Space Station | Xiao_Nanniang | WA | 0ms | 3696kb | C++17 | 1.9kb | 2024-06-24 15:21:15 | 2024-06-24 15:21:21 |
Judging History
answer
#include <iostream>
#define ll long long
const int MOD = 998244353;
using namespace std;
template<class T>
ll Pow(ll a, T b) {
ll res = 1;
while (b) {
if (b & 1) {
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return res;
}
ll Inv(ll a) {
return Pow(a, MOD - 2);
}
int Add(int a, int b) {
int res = a + b;
if (res < MOD) {
return res;
}
return res - MOD;
}
int n;
int m;
int cnt[101][10001];
int fac[101];
int invFac[101];
ll C(int a, int b) {
return (ll)fac[a] * invFac[a - b] % MOD * invFac[b] % MOD;
}
ll InvCn(int a, int b) {
return (ll)invFac[a] * fac[a - b] % MOD * fac[b - 1] % MOD;
}
void Init() {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = (ll)i * fac[i - 1] % MOD;
// cout << i << ' ' << fac[i] << endl;
}
invFac[n] = Inv(fac[n]);
for (int i = n; i > 0; i--) {
// cout << i << ' ' << invFac[i] << endl;
invFac[i - 1] = (ll)i * invFac[i] % MOD;
}
}
void Solve() {
cin >> n >> m;
Init();
cnt[0][0] = 1;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
for (int j = i; j > 0; j--) {
for (int l = 0; l <= (j - 1) * m; l++) {
int r = min(l + a, j * m);
cnt[j][r] = Add(cnt[j][r], cnt[j - 1][l]);
}
}
}
// cout << cnt[1][2] << endl;
ll res = 0;
for (int i = 1; i <= n; i++) {
ll cur = 0;
for (int j = 1; j <= i * m; j++) {
cur = (cur + (ll)j * cnt[i][j]) % MOD;
}
// cout << i << ' ' << cur << endl;
// cout << C(n, i) << endl;
res = (res + cur * InvCn(n, i)) % MOD;
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
3 3 2 3 4
output:
499122185
result:
ok 1 number(s): "499122185"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3696kb
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: 3612kb
input:
10 34 91 86 1 14 98 13 85 64 91 20
output:
919811177
result:
wrong answer 1st numbers differ - expected: '707882334', found: '919811177'