QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#119081 | #1911. Tree Depth | bashkort | 28.571429 | 15ms | 42336kb | C++20 | 2.2kb | 2023-07-04 20:52:19 | 2023-07-04 20:52:20 |
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]);
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'