QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636518#7875. Queue SortingAlphaZeWA 92ms4296kbC++202.1kb2024-10-13 00:14:242024-10-13 00:14:24

Judging History

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

  • [2024-10-13 00:14:24]
  • 评测
  • 测评结果:WA
  • 用时:92ms
  • 内存:4296kb
  • [2024-10-13 00:14:24]
  • 提交

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'