QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#122250	#1911. Tree Depth	bashkort	0	0ms	0kb	C++20	2.2kb	2023-07-09 21:22:58	2023-07-09 21:23:00

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-09 21:23:00]
评测

测评结果：0
用时：0ms
内存：0kb

查看

[2023-07-09 21:22:58]
提交

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);
				assert(now == dp[len][inv]);
                sv[inv] = now;
                if (inv <= k) {
                    madd(ans[i], 1LL * now * add[n - i - 1][k - inv] % MOD);
                }
                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] % MOD);
                }
                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;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 0

Dangerous Syscalls

input:

3 0 192603497

output:

result:

Test #2:

score: 0

Dangerous Syscalls

input:

50 696 750243917

output:

result:

Test #3:

score: 0

Dangerous Syscalls

input:

297 15802 727196621

output:

result:

Test #4:

score: 0

Dangerous Syscalls

input:

298 21805 239769737

output:

result:

Test #5:

score: 0

Dangerous Syscalls

input:

299 19637 130617143

output:

result:

Test #6:

score: 0

Dangerous Syscalls

input:

300 24244 397758089

output:

result:

Test #7:

score: 0

Dangerous Syscalls

input:

3 1 144408983

output:

result:

Test #8:

score: 0

Dangerous Syscalls

input:

7 15 920024579

output:

result:

Test #9:

score: 0

Dangerous Syscalls

input:

8 10 841786427

output:

result:

Test #10:

score: 0

Dangerous Syscalls

input:

18 117 592996081

output:

result:

Test #11:

score: 0

Dangerous Syscalls

input:

19 85 794215811

output:

result:

Test #12:

score: 0

Dangerous Syscalls

input:

20 110 531627143

output:

result:

Test #13:

score: 0

Dangerous Syscalls

input:

48 657 654131603

output:

result:

Test #14:

score: 0

Dangerous Syscalls

input:

49 843 343647949