QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86599#4807. Melborp Lacissalccodicon#WA 35ms19988kbC++202.0kb2023-03-10 11:44:402023-03-10 11:44:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-10 11:44:45]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:19988kb
  • [2023-03-10 11:44:40]
  • 提交

answer

//
// Created by codicon on 3/9/2023 at 6:56 PM.
//

// The idea is that there is a bijection between the n + 1prefix sums and the n values of the array

#include <bits/stdc++.h>

using namespace std;

# define add(a, b) a = ((a) + (b)) % MOD;

int n, k, t;

const int MAXN = 64, MOD =  998'244'353;

int dp[MAXN + 1][MAXN + 2][(MAXN)*(MAXN+1)/2 + 1];

long long FAC[MAXN+1], INV_FAC[MAXN+1];

long long binexp(long long b, int e) {
    long long res = 1;

    for (; e; b = b * b % MOD, e >>= 1) {
        if (e&1) res = res * b % MOD;
    }

    return res;
}

void set_up() {
    FAC[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        FAC[i] = FAC[i-1] * i % MOD;
    }

    INV_FAC[MAXN] = binexp(FAC[MAXN], MOD-2);
    for (int i = MAXN-1; i >= 0; i--) {
        INV_FAC[i] = INV_FAC[i+1] * (i+1) % MOD;
    }
}

long long choose(int n, int k) {
    if (k > n) {
        return 0;
    }

    return (FAC[n] * INV_FAC[k] % MOD) * INV_FAC[n-k] % MOD;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k >> t;

    set_up();

    // Base case
    for (int used = 1; used <= n+1; used++) {
        dp[1][used][choose(used, 2)] = 1;
    }

    // Do dp
    for (int pused = 1; pused < k; pused++) {
        for (int used = 1; used <= n+1; used++) {
            for (int goodness = 0; goodness <= t; goodness++) {
                // Don't use prefix value
                add(dp[pused + 1][used][goodness], dp[pused][used][goodness])

                // Use prefix value
                for (int new_used = 1;
                        new_used + used <= n+1 and
                            goodness + choose(new_used, 2) <= t;
                        new_used++) {
                    add(dp[pused + 1][used + new_used][goodness + choose(new_used, 2)],
                        dp[pused][used][goodness] * choose(used-1 + new_used, new_used) % MOD)
                }
            }
        }
    }

    cout << dp[k][n+1][t];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 5 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

7 10 15

output:

2016

result:

ok 1 number(s): "2016"

Test #3:

score: 0
Accepted
time: 35ms
memory: 15784kb

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

score: -100
Wrong Answer
time: 8ms
memory: 19988kb

input:

64 64 0

output:

1

result:

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