QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119081#1911. Tree Depthbashkort28.571429 15ms42336kbC++202.2kb2023-07-04 20:52:192023-07-04 20:52:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-04 20:52:20]
  • 评测
  • 测评结果:28.571429
  • 用时:15ms
  • 内存:42336kb
  • [2023-07-04 20:52:19]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 301;

int add[N][N * N], dp[N][N * N], MOD, ans[N], sv[N * N];

void madd(int &x, int y) {
    if ((x += y) >= MOD) {
        x -= MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k >> MOD;

    add[0][0] = dp[0][0] = 1;

    for (int x = 1; x <= n; ++x) {
        int sum = 0;
        for (int i = 0; i < n * n; ++i) {
            madd(sum, dp[x - 1][i]);
            if (i - x >= 0) {
                madd(sum, MOD - dp[x - 1][i - x]);
            }
            dp[x][i] = sum;
        }
        sum = 0;
        for (int i = 0; i < n * n; ++i) {
            madd(sum, add[x - 1][i]);
            if (i - (n - x) - 1 >= 0) {
                madd(sum, MOD - add[x - 1][i - (n - x) - 1]);
            }
            add[x][i] = sum;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i; j >= 0; --j) {
            int sub = 0, len = i - j;
            for (int inv = 0; inv < n * n; ++inv) {
                int now = dp[i + 1][inv];
                madd(now, MOD - sub);
                sv[inv] = now;
                if (inv <= k) {
                    madd(ans[i], 1LL * now * add[n - i - 1][k - inv]);
                }
                madd(sub, now);
                if (inv - len >= 0) {
                    madd(sub, MOD - sv[inv - len]);
                }
            }
        }
        for (int j = i + 1; j < n; ++j) {
            int sub = 0, len = j - i;
            for (int inv = n * (n - 1) / 2; inv >= 0; --inv) {
                int now = dp[n - i][inv];
                madd(now, MOD - sub);
                sv[inv] = now;
                if (inv <= k) {
                    madd(ans[i], 1LL * now * add[i][k - inv]);
                }
                madd(sub, now);
                if (inv + len < n * n) {
                    madd(sub, MOD - sv[inv + len]);
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i];
        if (i + 1 < n) {
            cout << " ";
        }
    }

    return 0;
}

详细

Test #1:

score: 7.14286
Accepted
time: 0ms
memory: 7424kb

input:

3 0 192603497

output:

1 2 3

result:

ok single line: '1 2 3'

Test #2:

score: 0
Wrong Answer
time: 15ms
memory: 38316kb

input:

50 696 750243917

output:

449512793 49444624 520258482 272580934 335685446 -1231713498 377505777 673696903 -457956474 230362363 367972053 -1122640782 93111834 -366801514 13560599 451758620 -390996056 547108431 -94085876 -1109135773 745802419 377044536 173942101 428939287 -202196683 680320676 -971488922 607687619 -344379370 2...

result:

wrong answer 1st lines differ - expected: '449512793 49444624 712564120 6...4 667850178 450716250 361140820', found: '449512793 49444624 520258482 2...2 574318794 450716250 361140820'

Test #3:

score: 0
Time Limit Exceeded

input:

297 15802 727196621

output:


result:


Test #4:

score: 0
Time Limit Exceeded

input:

298 21805 239769737

output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

299 19637 130617143

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

300 24244 397758089

output:


result:


Test #7:

score: 7.14286
Accepted
time: 0ms
memory: 9472kb

input:

3 1 144408983

output:

3 4 4

result:

ok single line: '3 4 4'

Test #8:

score: 7.14286
Accepted
time: 3ms
memory: 13644kb

input:

7 15 920024579

output:

913 928 891 825 735 620 467

result:

ok single line: '913 928 891 825 735 620 467'

Test #9:

score: 7.14286
Accepted
time: 2ms
memory: 9564kb

input:

8 10 841786427

output:

5233 6569 7487 8150 8608 8851 8810 8275

result:

ok single line: '5233 6569 7487 8150 8608 8851 8810 8275'

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 17880kb

input:

18 117 592996081

output:

547877949 145016137 548274945 -14715748 277504730 234345664 527309591 -6176818 370484454 357814813 153814889 -1358760068 -1794352102 315219693 309739417 541138573 2891403 164502295

result:

wrong answer 1st lines differ - expected: '547877949 145016137 11583074 3...805 107852039 2891403 164502295', found: '547877949 145016137 548274945 ...417 541138573 2891403 164502295'

Test #11:

score: 0
Wrong Answer
time: 4ms
memory: 21828kb

input:

19 85 794215811

output:

511056080 637508276 328224260 359776750 33034059 1630805 64723214 497411677 -614602311 744910662 303456918 106358436 -271371486 -1049129342 718503044 474896624 59845850 84890253 330316897

result:

wrong answer 1st lines differ - expected: '511056080 637508276 190300150 ...981 76969655 84890253 330316897', found: '511056080 637508276 328224260 ...624 59845850 84890253 330316897'

Test #12:

score: 0
Wrong Answer
time: 4ms
memory: 21788kb

input:

20 110 531627143

output:

521698138 54185119 -196530256 239075277 -1848795796 -813931347 52939119 4827874 148267156 93271711 331983592 219023260 202312187 119161454 234394004 149802257 101459442 415768719 298360142 55649023

result:

wrong answer 1st lines differ - expected: '521698138 54185119 383790995 1...003 15960335 298360142 55649023', found: '521698138 54185119 -196530256 ...42 415768719 298360142 55649023'

Test #13:

score: 0
Wrong Answer
time: 15ms
memory: 40260kb

input:

48 657 654131603

output:

521761918 590764411 143297216 632611170 520608954 613259791 40038457 204243321 127101845 -1738892746 -195519531 -847684245 -689894549 572670602 66216406 284877984 199744412 -1248381401 -924294363 -1686520444 -671412686 -154658664 630599119 394012293 -709750059 -1527774642 -471584140 -876914801 -1490...

result:

wrong answer 1st lines differ - expected: '521761918 590764411 362110594 ...1 112206928 524726208 537089328', found: '521761918 590764411 143297216 ...5 363388449 524726208 537089328'

Test #14:

score: 0
Wrong Answer
time: 13ms
memory: 42336kb

input:

49 843 343647949

output:

120757277 77103521 136542041 -763684654 -1152785541 -1109250159 79092513 188860110 16723533 153722433 284737021 277734825 110560534 46019633 281494725 306773250 111600060 -504315553 190221496 51454332 216372758 289790576 4669832 -2018307873 -1109637620 139219957 -174481099 -1844289133 164766420 -171...

result:

wrong answer 1st lines differ - expected: '120757277 77103521 35835898 12...28 287619876 258731922 21182719', found: '120757277 77103521 136542041 -...51 279076628 258731922 21182719'