QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#119082 | #1911. Tree Depth | bashkort | 71.428571 | 23ms | 42324kb | C++20 | 2.2kb | 2023-07-04 20:53:07 | 2023-07-04 20:53:07 |
Judging History
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] % 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 7.14286
Accepted
time: 1ms
memory: 7448kb
input:
3 0 192603497
output:
1 2 3
result:
ok single line: '1 2 3'
Test #2:
score: 7.14286
Accepted
time: 16ms
memory: 42324kb
input:
50 696 750243917
output:
449512793 49444624 712564120 694762313 239306371 253603336 533190451 398369069 361526878 278308623 574792922 277515625 508820514 723503007 402637769 428971841 387173861 602711957 735429052 173792097 269181379 145740025 392058578 592248870 293782098 625912579 74241665 341952508 388359865 11575395 162...
result:
ok single line: '449512793 49444624 712564120 6...4 667850178 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: 2ms
memory: 9564kb
input:
3 1 144408983
output:
3 4 4
result:
ok single line: '3 4 4'
Test #8:
score: 7.14286
Accepted
time: 1ms
memory: 11680kb
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: 7.14286
Accepted
time: 1ms
memory: 19760kb
input:
18 117 592996081
output:
547877949 145016137 11583074 378068048 117925164 107498081 166172066 12316002 551291515 285969093 566307198 348339128 63253558 210555336 109483805 107852039 2891403 164502295
result:
ok single line: '547877949 145016137 11583074 3...805 107852039 2891403 164502295'
Test #11:
score: 7.14286
Accepted
time: 0ms
memory: 17860kb
input:
19 85 794215811
output:
511056080 637508276 190300150 29210812 510749361 355748507 413475756 620017804 752917392 404850167 616149292 578505796 178005322 617303400 202137717 65000981 76969655 84890253 330316897
result:
ok single line: '511056080 637508276 190300150 ...981 76969655 84890253 330316897'
Test #12:
score: 7.14286
Accepted
time: 1ms
memory: 21820kb
input:
20 110 531627143
output:
521698138 54185119 383790995 125356097 186996122 507946400 519492165 6290825 371285862 81568004 351223842 523847702 287006750 172524202 316711790 370641576 417864003 15960335 298360142 55649023
result:
ok single line: '521698138 54185119 383790995 1...003 15960335 298360142 55649023'
Test #13:
score: 7.14286
Accepted
time: 12ms
memory: 38268kb
input:
48 657 654131603
output:
521761918 590764411 362110594 271651449 522825518 614035606 496292487 204525574 30896840 328013007 110745415 37147159 544084974 17707417 615624424 208844937 550741658 496165179 11267815 540257553 416633612 465813784 632831939 318541790 499258264 189205995 383416814 308463326 66063684 284604967 27492...
result:
ok single line: '521761918 590764411 362110594 ...1 112206928 524726208 537089328'
Test #14:
score: 7.14286
Accepted
time: 23ms
memory: 42304kb
input:
49 843 343647949
output:
120757277 77103521 35835898 128975015 235812643 106808742 216028805 18726066 84134625 20268195 281451802 161450133 275259235 115134432 4449149 199813180 121762773 250026807 131614073 103004058 136607537 332402181 200780627 127537848 119189400 298169337 11950053 3478854 267676071 197536465 121537072 ...
result:
ok single line: '120757277 77103521 35835898 12...28 287619876 258731922 21182719'