QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636518 | #7875. Queue Sorting | AlphaZe | WA | 92ms | 4296kb | C++20 | 2.1kb | 2024-10-13 00:14:24 | 2024-10-13 00:14:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int N = 505;
const int mod = 998244353;
void AddMod(int &p, int k) { p = (p + k) % mod; }
int n, a[N], pre[N], f[N][N];
int fac[N], ifac[N];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
int C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return 1ll * (1ll * fac[n] * ifac[n - m] % mod) * ifac[m] % mod;
}
int main() {
// freopen("in.txt", "r", stdin);
fac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[N - 1] = qpow(fac[N - 1], mod - 2);
for (int i = N - 2; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
n = read();
for (int i = 1; i <= n; ++i) a[i] = read(), pre[i] = pre[i - 1] + a[i];
f[1][0] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= pre[i]; ++j) {
if (!f[i][j]) continue;
if (j) {
for (int x = 0; x < a[i + 1]; ++x) {
for (int k = 1; k <= j - 1; ++k) {
AddMod(f[i + 1][x + k + 1],
1ll * f[i][j] * C(j - k - 1 + a[i + 1] - x - 1, a[i + 1] - x - 1) % mod);
}
}
AddMod(f[i + 1][j + a[i + 1]], f[i][j]);
} else {
if (a[i + 1]) {
for (int k = 1; k <= pre[i]; ++k) {
AddMod(f[i + 1][k + 1], 1ll * f[i][0] * C(pre[i + 1] - (k + 1), a[i + 1] - 1) % mod);
}
}
AddMod(f[i + 1][0], f[i][0]);
}
}
// for (int j = 0; j <= pre[i + 1]; ++j)
}
int ans = 0;
for (int j = 0; j <= pre[n]; ++j) AddMod(ans, f[n][j]);
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 92ms
memory: 4296kb
input:
300 0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...
output:
234930213
result:
wrong answer 1st numbers differ - expected: '507010274', found: '234930213'