QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636540#7875. Queue SortingAlphaZeTL 0ms0kbC++202.2kb2024-10-13 00:24:402024-10-13 00:24:40

Judging History

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

  • [2024-10-13 00:24:40]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: