QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636540 | #7875. Queue Sorting | AlphaZe | TL | 0ms | 0kb | C++20 | 2.2kb | 2024-10-13 00:24:40 | 2024-10-13 00:24:40 |
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 {
for (int x = 0; x < a[i + 1]; ++x) {
for (int k = 1; k <= pre[i]; ++k) {
AddMod(f[i + 1][x + k + 1],
1ll * f[i][j] * C(pre[i + 1] - x - (k + 1), a[i + 1] - x - 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: 0
Time Limit Exceeded
input:
4 1 1 1 1