QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#118629 | #1911. Tree Depth | pandapythoner# | 100 ✓ | 434ms | 75232kb | C++20 | 5.1kb | 2023-07-03 19:36:48 | 2024-05-31 18:54:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define lll __int128_t
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e18;
mt19937 rnd(234);
int n, k;
ll m;
pair<ll, ll> operator+(const pair<ll, ll> &a, const pair<ll, ll> &b) {
return make_pair((a.first + b.first) % m, (a.second + b.second) % m);
}
pair<ll, ll> operator-(const pair<ll, ll> &a, const pair<ll, ll> &b) {
return make_pair((a.first + m - b.first) % m, (a.second + m - b.second) % m);
}
vector<ll> get_biba_slow(int n, int k, ll bebra) {
vector<ll> rs(n);
for (int i = 0; i < n; i += 1) {
vector<pair<ll, ll>> dp = {{1, bebra}};
int dp_sz = (int)dp.size();
for (int j = 1; j <= i; j += 1) {
pair<ll, ll> sm = {0, 0};
int l = 0;
int r = 0;
vector<pair<ll, ll>> new_dp(dp_sz + j);
int new_dp_sz = dp_sz + j;
for (int t = 0; t < new_dp_sz; t += 1) {
while (r < min(t + 1, dp_sz)) {
sm = (sm + dp[r]);
r += 1;
}
while (l < max(0, t - j)) {
sm = (sm - dp[l]);
l += 1;
}
new_dp[t] = sm;
}
for (int t = 0; t < dp_sz; t += 1) {
new_dp[t] = (new_dp[t] + make_pair(0, dp[t].first));
}
dp.swap(new_dp);
dp_sz = (int)dp.size();
}
for (int j = i + 1; j <= n - 1; j += 1) {
pair<ll, ll> sm = {0, 0};
int l = 0;
int r = 0;
vector<pair<ll, ll>> new_dp(dp_sz + j);
int new_dp_sz = dp_sz + j;
for (int t = 0; t < new_dp_sz; t += 1) {
while (r < min(t + 1, dp_sz)) {
sm = (sm + dp[r]);
r += 1;
}
while (l < max(0, t - j)) {
sm = (sm - dp[l]);
l += 1;
}
new_dp[t] = sm;
}
dp.swap(new_dp);
dp_sz = (int)dp.size();
}
if (k < dp_sz) {
rs[i] = dp[k].second;
}
}
return rs;
}
vector<ll> solve_slow() {
vector<ll> a = get_biba_slow(n, k, 1);
vector<ll> b = get_biba_slow(n, n * (n - 1) / 2 - k, 0);
reverse(all(b));
vector<ll> c(n);
for (int i = 0; i < n; i += 1) {
c[i] = (a[i] + b[i]) % m;
}
return c;
}
vector<ll> get_biba(int n, int k, ll bebra) {
vector<vector<ll>> dp_aboba(n + 1);
dp_aboba[n] = {1};
int dp_sz = 1;
for (int j = n - 1; j >= 1; j -= 1) {
ll sm = 0;
int l = 0;
int r = 0;
int new_dp_sz = dp_sz + j;
dp_aboba[j].resize(new_dp_sz);
for (int t = 0; t < new_dp_sz; t += 1) {
while (r < min(t + 1, dp_sz)) {
sm = (sm + dp_aboba[j + 1][r]) % m;
r += 1;
}
while (l < max(0, t - j)) {
sm = (sm + m - dp_aboba[j + 1][l]) % m;
l += 1;
}
dp_aboba[j][t] = sm;
}
dp_sz = new_dp_sz;
}
vector<ll> rs(n, 0);
vector<pair<ll, ll>> dp = {{1, bebra}};
dp_sz = 1;
for (int i = 0; i < n; i += 1) {
int dp_sz = (int)dp.size();
if(i > 0){
int j = i;
pair<ll, ll> sm = {0, 0};
int l = 0;
int r = 0;
vector<pair<ll, ll>> new_dp(dp_sz + j);
int new_dp_sz = dp_sz + j;
for (int t = 0; t < new_dp_sz; t += 1) {
while (r < min(t + 1, dp_sz)) {
sm = (sm + dp[r]);
r += 1;
}
while (l < max(0, t - j)) {
sm = (sm - dp[l]);
l += 1;
}
new_dp[t] = sm;
}
for (int t = 0; t < dp_sz; t += 1) {
new_dp[t] = (new_dp[t] + make_pair(0, dp[t].first));
}
dp.swap(new_dp);
dp_sz = (int)dp.size();
}
for(int cnt = 0; cnt < dp_sz && cnt <= k; cnt += 1){
int aboba_dp_sz = (int)dp_aboba[i + 1].size();
int cnt_aboba = k - cnt;
if(cnt_aboba < aboba_dp_sz){
rs[i] = (rs[i] + dp[cnt].second * dp_aboba[i + 1][cnt_aboba]) % m;
}
}
}
return rs;
}
vector<ll> solve() {
vector<ll> a = get_biba(n, k, 1);
vector<ll> b = get_biba(n, n * (n - 1) / 2 - k, 0);
reverse(all(b));
vector<ll> c(n);
for (int i = 0; i < n; i += 1) {
c[i] = (a[i] + b[i]) % m;
}
return c;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n >> k >> m;
auto rs = solve();
for (auto t : rs) {
cout << t << " ";
}
cout << "\n";
return 0;
}
详细
Test #1:
score: 7.14286
Accepted
time: 0ms
memory: 3496kb
input:
3 0 192603497
output:
1 2 3
result:
ok single line: '1 2 3 '
Test #2:
score: 7.14286
Accepted
time: 0ms
memory: 3924kb
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... 667850178 450716250 361140820 '
Test #3:
score: 7.14286
Accepted
time: 433ms
memory: 73148kb
input:
297 15802 727196621
output:
486276417 458979137 633220080 671742433 107673150 529324190 324747034 138414758 297407600 189451920 633810846 557701835 690685467 596872719 247590299 370607403 227689925 204180402 520872795 479183067 350187959 259391626 245397463 169577544 652520116 345923254 391218124 452020412 519284846 679835173 ...
result:
ok single line: '486276417 458979137 633220080 ... 104884298 168612877 661639443 '
Test #4:
score: 7.14286
Accepted
time: 420ms
memory: 73796kb
input:
298 21805 239769737
output:
35976286 81917297 65702975 166578991 157112038 118428459 38220321 50578071 25991238 53375839 64365771 175432823 8168913 81069441 10184624 26121316 186569952 239578352 37117541 212510990 151836426 32063985 159139561 16037907 87723509 46618613 122249870 130980064 143052098 131428325 213079112 21913600...
result:
ok single line: '35976286 81917297 65702975 166...22 99457032 95751202 156964893 '
Test #5:
score: 7.14286
Accepted
time: 425ms
memory: 74536kb
input:
299 19637 130617143
output:
36430393 42327716 63149503 87354540 22494848 64455589 121751906 51221493 69040045 20826276 14122623 33176720 74442015 113156449 48446215 77846035 76752035 10296909 35876762 8455875 105649870 116708605 86611234 47690206 43292107 35776393 23385495 128148266 94902511 28586103 45137893 96604589 42652113...
result:
ok single line: '36430393 42327716 63149503 873...488 34633954 89122561 83035860 '
Test #6:
score: 7.14286
Accepted
time: 434ms
memory: 75232kb
input:
300 24244 397758089
output:
205398472 345483517 133931835 67279473 356869968 264400165 322166510 95501821 223376073 154620688 364853048 188354306 5976340 112186690 96691087 385589645 347255465 97376862 186601071 388284057 171242619 353930913 121813457 37384050 274096385 11395198 61466483 168874805 224234104 137374799 254754260...
result:
ok single line: '205398472 345483517 133931835 ... 174607666 380173522 203819946 '
Test #7:
score: 7.14286
Accepted
time: 0ms
memory: 3844kb
input:
3 1 144408983
output:
3 4 4
result:
ok single line: '3 4 4 '
Test #8:
score: 7.14286
Accepted
time: 0ms
memory: 3840kb
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: 0ms
memory: 3728kb
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: 0ms
memory: 3644kb
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...05 107852039 2891403 164502295 '
Test #11:
score: 7.14286
Accepted
time: 0ms
memory: 3644kb
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 ...81 76969655 84890253 330316897 '
Test #12:
score: 7.14286
Accepted
time: 0ms
memory: 3848kb
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...03 15960335 298360142 55649023 '
Test #13:
score: 7.14286
Accepted
time: 2ms
memory: 3820kb
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 ... 112206928 524726208 537089328 '
Test #14:
score: 7.14286
Accepted
time: 2ms
memory: 3916kb
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...8 287619876 258731922 21182719 '