QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#350674#7875. Queue Sortingwtz2333WA 99ms9732kbC++171.9kb2024-03-11 00:10:062024-03-11 00:10:07

Judging History

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

  • [2024-03-11 00:10:07]
  • 评测
  • 测评结果:WA
  • 用时:99ms
  • 内存:9732kb
  • [2024-03-11 00:10:06]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 1010;

using ll = long long;
const int mo = 998244353;

int C[maxn][maxn];
int dp[maxn][maxn];

void upd(int &x,int y) {
    (x += y) >= mo ? (x -= mo) : x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a;
    for(int i = 1;i <= n;i ++) {
        int x;
        cin >> x;
        if(x) a.push_back(x);
    }
    n = a.size();
    if(n == 0) {
        cout << 1 << endl;
        return 0;
    }
    C[0][0] = 1;
    for(int i = 1;i <= 1000;i ++) {
        C[i][0] = 1;
        for(int j = 1;j <= i;j ++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;
        }
    }
    auto calc = [&](int m,int n) {
        if(n == 0) return 1;
        return C[n + m - 1][n - 1];
    };
    // cerr << n << endl;
    dp[n][a.back()] = 1;
    int sum = a.back();
    for(int i = n - 1;i >= 1;i --) {
        for(int j = 1;j <= sum;j ++) {

            for(int k = 1;k <= a[i - 1];k ++) {
                for(int p = 1;p <= j;p ++) {
                    int endlen = j - p + 1;
                    upd(dp[i][endlen + a[i - 1] - k],1ll * dp[i + 1][j] * calc(k - 1,j) % mo);
                    // upd(dp[i][k + p],1ll * dp[i + 1][j] * calc(k,j,p) % mo); 
                    // cerr << i + 1 << " " << j << " " << dp[i + 1][j] << endl;
                    // cerr << i << " " << k + p << " " << dp[i][k + p] << endl;
                    // cerr << endl;
                }
            }
            upd(dp[i][j + a[i - 1]],dp[i + 1][j]);
            // cerr << endl;
            // cerr << i << " " << j << " " << dp[i][j] << endl;
            // cerr << endl;

        }
        sum += a[i - 1];
    }
    ll ans = 0;
    for(int i = 1;i <= sum;i ++) ans = (ans + dp[1][i]) % mo;
    cout << ans << endl;
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9732kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 99ms
memory: 9296kb

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:

295951759

result:

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