QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666994#7875. Queue SortingCalculateloveWA 70ms4444kbC++141.5kb2024-10-22 20:41:302024-10-22 20:41:41

Judging History

This is the latest submission verdict.

  • [2024-10-22 20:41:41]
  • Judged
  • Verdict: WA
  • Time: 70ms
  • Memory: 4444kb
  • [2024-10-22 20:41:30]
  • Submitted

answer

#include <bits/stdc++.h>

const int N = 510;
const int mod = 998244353;

int qpow(int a, int b, int p) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
    }
    return ans;
}

int n;
int a[N], pre[N];

int fact[N], facv[N];
void fact_init(const int &n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i ++) fact[i] = 1ll * fact[i - 1] * i % mod;

    facv[n] = qpow(fact[n], mod - 2, mod);
    for (int i = n - 1; i >= 0; i --) facv[i] = 1ll * facv[i + 1] * (i + 1) % mod;
}

int binom(int n, int m) {
    if (n < m || m < 0) return 0;
    return 1ll * facv[m] * facv[n - m] % mod * fact[n] % mod;
}

int f[N][N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++)
        pre[i] = pre[i - 1] + a[i];

    fact_init(n);

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= pre[i - 1]; j ++) {
            f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
            for (int x = 1; x <= a[i]; x ++) {
                for (int k = j + 1; k <= pre[i - 1]; k ++) {
                    f[i][x + k - 1] = (f[i][x + k - 1] + 1ll * f[i - 1][j] * binom(x + k - j - 2, x - 1)) % mod;
                }
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= pre[n]; j ++) ans = (ans + f[n][j]) % mod;

    printf("%d\n", ans);

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 70ms
memory: 4444kb

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:

655368591

result:

wrong answer 1st numbers differ - expected: '507010274', found: '655368591'