2237.md (19515B)
1 Source: https://codeforces.com/blog/entry/154603 2 3 Thank you for participating! We hope you enjoyed the problems. 4 5 [2237A - Destroying Towers](/contest/2237/problem/A) 6 7 Idea: [_ja](/profile/_ja "Master _ja") Preparation: [_ja](/profile/_ja "Master _ja") & [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 int main() { 21 int t; 22 cin >> t; 23 while (t--) { 24 int n; 25 cin >> n; 26 int x = 10000, y = 0; 27 for (int i = 0; i < n; ++i) { 28 int z; 29 cin >> z; 30 x = min(x, z), y += x; 31 } 32 cout << y << '\n'; 33 } 34 return 0; 35 } 36 ``` 37 38 [2237B - Annoying the Ghost](/contest/2237/problem/B) 39 40 Idea: [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") Preparation: [_ja](/profile/_ja "Master _ja") & [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") & [Boboge](/profile/Boboge "Grandmaster Boboge") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Implementation** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 int main() { 54 int t; 55 cin >> t; 56 while (t--) { 57 int n; 58 cin >> n; 59 vector<int> a(n), c(n); 60 for (int i = 0; i < n; i++) cin >> a[i]; 61 set<int> s; 62 for (int i = 0; i < n; i++) { 63 int x; 64 cin >> x; 65 s.insert(x); 66 } 67 bool y = true; 68 for (int i = 0; i < n; ++i) { 69 auto it = s.lower_bound(a[i]); 70 if (it == s.end()) { 71 y = false; 72 break; 73 } 74 c[i] = *it; 75 s.erase(it); 76 } 77 if (!y) { 78 cout << -1 << '\n'; 79 continue; 80 } 81 int ans = 0; 82 for (int i = 0; i < n; ++i) { 83 for (int j = i + 1; j < n; ++j) { 84 if (c[i] > c[j]) { 85 ans++; 86 } 87 } 88 } 89 cout << ans << '\n'; 90 } 91 return 0; 92 } 93 ``` 94 95 [2237C - Duck Surplus](/contest/2237/problem/C) 96 97 Idea: [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") Preparation: [Boboge](/profile/Boboge "Grandmaster Boboge") 98 99 **Tutorial** 100 101 Tutorial is loading... 102 103 **Implementation** 104 105 ``` 106 #include <bits/stdc++.h> 107 108 using namespace std; 109 110 using i64 = long long; 111 112 void run() { 113 int n; 114 cin >> n; 115 vector<int> a(n); 116 for (int i = 0; i < n; ++i) { 117 cin >> a[i]; 118 } 119 i64 ans = 0; 120 for (int i = 0; i < n; ++i) { 121 if (ans > a[i]) { 122 ans += a[i]; 123 } else { 124 ans = a[i]; 125 } 126 } 127 cout << ans << '\n'; 128 } 129 130 int main() { 131 ios_base::sync_with_stdio(false); 132 cin.tie(nullptr); 133 int T = 1; 134 cin >> T; 135 while (T--) { 136 run(); 137 } 138 return 0; 139 } 140 ``` 141 142 [2237D - Fullmetal Bitchemist](/contest/2237/problem/D) 143 144 Idea: [zeemanz](/profile/zeemanz "Grandmaster zeemanz") Preparation: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 145 146 **Tutorial** 147 148 Tutorial is loading... 149 150 **Implementation(python)** 151 152 ``` 153 for _ in range(int(input())): 154 n = int(input()) 155 a = [1, 0, 0] 156 x = 0 157 ans = 0 158 pre = "" 159 y = 0 160 for c in input(): 161 if c == "0": 162 x -= 1 163 else: 164 x += 1 165 x %= 3 166 if c == pre: 167 y = 1 168 else: 169 y += 1 170 pre = c 171 ans += sum(a) - a[x] 172 a[x] += 1 173 ans -= (y - 1) // 2 174 print(ans) 175 ``` 176 177 [2237E - Permutation Commutation](/contest/2237/problem/E) 178 179 Idea: [_ja](/profile/_ja "Master _ja") Preparation: [Boboge](/profile/Boboge "Grandmaster Boboge") 180 181 **Tutorial** 182 183 Tutorial is loading... 184 185 **Implementation** 186 187 ``` 188 #include <bits/stdc++.h> 189 190 using namespace std; 191 192 void run(int testCase) { 193 int n; 194 cin >> n; 195 vector<int> a(n), b(n); 196 for (int i = 0; i < n; ++i) { 197 cin >> a[i]; 198 a[i]--; 199 } 200 for (int i = 0; i < n; ++i) { 201 cin >> b[i]; 202 if (b[i] != -1) { 203 b[i]--; 204 } 205 } 206 vector<int> vis(n); 207 for (int i = 0; i < n; ++i) { 208 if (b[i] != -1 and !vis[i]) { 209 int j = i; 210 while (true) { 211 if (vis[j]) break; 212 vis[j] = 1; 213 if (b[a[j]] == -1) { 214 b[a[j]] = a[b[j]]; 215 } else if (b[a[j]] != a[b[j]]) { 216 cout << "NO\n"; 217 return; 218 } 219 j = a[j]; 220 } 221 } 222 } 223 vector<int> cnt(n); 224 for (int i = 0; i < n; ++i) { 225 if (b[i] == -1) continue; 226 cnt[b[i]]++; 227 } 228 for (int i = 0; i < n; ++i) { 229 if (cnt[i] > 1) { 230 cout << "NO\n"; 231 return; 232 } 233 } 234 vector<int> vis1(n), vis2(n); 235 vector<vector<int>> cycle1(n + 1), cycle2(n + 1); 236 for (int i = 0; i < n; ++i) { 237 if (b[i] == -1 and !vis1[i]) { 238 int j = i, len = 0; 239 while (!vis1[j]) { 240 vis1[j] = 1; 241 len++; 242 j = a[j]; 243 } 244 cycle1[len].push_back(i); 245 } 246 } 247 for (int i = 0; i < n; ++i) { 248 if (cnt[i] == 0 and !vis2[i]) { 249 int j = i, len = 0; 250 while (!vis2[j]) { 251 vis2[j] = 1; 252 len++; 253 j = a[j]; 254 } 255 cycle2[len].push_back(i); 256 } 257 } 258 for (int len = 1; len <= n; ++len) { 259 for (int i = 0; i < cycle1[len].size(); ++i) { 260 int x = cycle1[len][i], y = cycle2[len][i]; 261 while (b[x] == -1) { 262 b[x] = y; 263 x = a[x]; 264 y = a[y]; 265 } 266 } 267 } 268 cout << "YES\n"; 269 for (int i = 0; i < n; ++i) { 270 cout << b[i] + 1 << " \n"[i == n - 1]; 271 } 272 } 273 274 int main() { 275 ios_base::sync_with_stdio(false); 276 cin.tie(nullptr); 277 int T = 1; 278 cin >> T; 279 for (int t = 1; t <= T; ++t) { 280 run(t); 281 } 282 return 0; 283 } 284 ``` 285 286 [2237F - Paint the Array](/contest/2237/problem/F) 287 288 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") 289 290 **Tutorial** 291 292 Tutorial is loading... 293 294 **Implementation** 295 296 ``` 297 #include<bits/stdc++.h> 298 299 using namespace std; 300 int a[500000], pref[500001], suf[500001], dpvl[500001], inf = 1000000000; 301 302 int main() { 303 ios::sync_with_stdio(false), cin.tie(0); 304 int T, n, m, i, c; 305 for (cin >> T; T > 0; T--) { 306 cin >> n >> m; 307 for (i = 0; i < n; i++) { 308 cin >> a[i]; 309 a[i]--; 310 } 311 for (i = 0; i <= n; i++) { 312 pref[i] = -inf; 313 suf[i] = -inf; 314 dpvl[i] = -inf; 315 } 316 pref[0] = 0; 317 for (i = 0; i < n; i++) { 318 c = suf[i]; 319 if (i - a[i] >= 0) { 320 c = max(c, dpvl[i - a[i]]); 321 c = max(c, pref[i - a[i]]); 322 } 323 c++; 324 pref[i + 1] = max(pref[i], c); 325 suf[i + 1] = max(suf[i + 1], suf[i]); 326 if (i - a[i] >= 0)dpvl[i - a[i]] = max(dpvl[i - a[i]], c); 327 if (i - a[i] + m <= n)suf[i - a[i] + m] = max(suf[i - a[i] + m], c); 328 } 329 cout << n - max(suf[n], 0) << '\n'; 330 } 331 return 0; 332 } 333 ``` 334 335 [2237G - Send GCDs](/contest/2237/problem/G) 336 337 Idea: [_ja](/profile/_ja "Master _ja") Preparation: [Boboge](/profile/Boboge "Grandmaster Boboge") 338 339 **Tutorial** 340 341 Tutorial is loading... 342 343 **Implementation** 344 345 ``` 346 #include <bits/stdc++.h> 347 348 #define sz(a) (int)(a).size() 349 350 using namespace std; 351 352 using i64 = long long; 353 354 string type; 355 356 constexpr int P = 110; 357 constexpr int N = 1e6; 358 constexpr int sz_v = (1 << 18); 359 360 vector<int> ps, pks, v; 361 array<int, N + 1> idx; 362 363 void init() { 364 vector<int> max_p(N + 1); 365 max_p[1] = 1; 366 for (int i = 2; i <= N; ++i) { 367 if (max_p[i] == 0) { 368 ps.push_back(i); 369 for (int j = i; j <= N; j += i) { 370 max_p[j] = i; 371 } 372 } 373 } 374 ps.resize(P); 375 for (int p: ps) { 376 int x = p; 377 while (x * p <= N) x *= p; 378 pks.push_back(x); 379 } 380 for (int i = 1; i <= N and sz(v) < sz_v; ++i) { 381 if (max_p[i] <= ps.back()) { 382 v.push_back(i); 383 } 384 } 385 assert(sz(v) == sz_v); 386 for (int i = 0; i < sz(v); ++i) idx[v[i]] = i; 387 } 388 389 void run1() { 390 int n; 391 cin >> n; 392 vector<int> a(n); 393 for (int i = 0; i < n; ++i) { 394 cin >> a[i]; 395 } 396 vector<int> b; 397 for (int pk: pks) b.push_back(pk); 398 vector<int> bits; 399 for (int i = 0; i < n; ++i) { 400 for (int j = 19; j >= 0; --j) { 401 bits.push_back(a[i] >> j & 1); 402 } 403 } 404 while (sz(bits) % 18) bits.push_back(0); 405 for (int i = 0; i < sz(bits); i += 18) { 406 int now = 0; 407 for (int j = 0; j < 18; ++j) { 408 now *= 2; 409 now += bits[i + j]; 410 } 411 b.push_back(v[now]); 412 } 413 int k = sz(b); 414 cout << k << '\n'; 415 for (int i = 0; i < k; ++i) cout << b[i] << ' '; 416 cout << '\n'; 417 } 418 419 void run2() { 420 int n, k; 421 cin >> n >> k; 422 auto ask = [&](int i, int j) { 423 assert(i != j); 424 cout << "? " << i + 1 << ' ' << j + 1 << endl; 425 int g; 426 cin >> g; 427 return g; 428 }; 429 vector<int> bits; 430 for (int i = P; i < k; ++i) { 431 int x = 1; 432 for (int j = 0; j < P; ++j) { 433 int g = ask(i, j); 434 x *= g; 435 } 436 int now = idx[x]; 437 for (int j = 17; j >= 0; --j) { 438 bits.push_back(now >> j & 1); 439 } 440 } 441 vector<int> a(n); 442 for (int i = 0, j = 0; i < n; ++i, j += 20) { 443 int now = 0; 444 for (int x = 0; x < 20; ++x) { 445 now *= 2; 446 now += bits[j + x]; 447 } 448 a[i] = now; 449 } 450 cout << "!"; 451 for (int i = 0; i < n; ++i) cout << ' ' << a[i]; 452 cout << endl; 453 } 454 455 int main() { 456 ios_base::sync_with_stdio(false); 457 cin.tie(nullptr); 458 init(); 459 cin >> type; 460 int T = 1; 461 cin >> T; 462 while (T--) { 463 if (type == "first") { 464 run1(); 465 } else { 466 run2(); 467 } 468 } 469 return 0; 470 } 471 ``` 472 473 [2237H - Slime and Queries](/contest/2237/problem/H) 474 475 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") 476 477 **Tutorial** 478 479 Tutorial is loading... 480 481 **Implementation** 482 483 ``` 484 #include<bits/stdc++.h> 485 486 using namespace std; 487 vector<int> line[100000]; 488 int dfn[100000], siz[100000], fa[100000], wp[100000], tp[100000], dep[100000], cdfn; 489 490 void dfs1(int t, int f) { 491 vector<int>::iterator it; 492 int mx = -1; 493 fa[t] = f; 494 siz[t] = 1; 495 wp[t] = -1; 496 for (it = line[t].begin(); it != line[t].end(); it++) { 497 if ((*it) == f)continue; 498 dep[*it] = dep[t] + 1; 499 dfs1(*it, t); 500 siz[t] += siz[*it]; 501 if (siz[*it] > mx) { 502 mx = siz[*it]; 503 wp[t] = *it; 504 } 505 } 506 } 507 508 void dfs2(int t, int f) { 509 vector<int>::iterator it; 510 dfn[t] = cdfn; 511 cdfn++; 512 if (wp[t] == -1)return; 513 tp[wp[t]] = tp[t]; 514 dfs2(wp[t], t); 515 for (it = line[t].begin(); it != line[t].end(); it++) { 516 if ((*it) == f)continue; 517 if (*it == wp[t])continue; 518 tp[*it] = *it; 519 dfs2(*it, t); 520 } 521 } 522 523 map<int, int> mp, sg; 524 525 void access(int p) { 526 map<int, int>::iterator it; 527 int x; 528 it = sg.upper_bound(p); 529 it--; 530 x = (*it).second; 531 sg[p] = x; 532 } 533 534 int chkmap(int c, int vl) { 535 map<int, int>::iterator it; 536 int d; 537 while (1) { 538 it = mp.upper_bound(vl); 539 if (it == mp.begin())break; 540 it--; 541 d = min((*it).second, c); 542 c -= d; 543 (*it).second -= d; 544 if ((*it).second == 0)mp.erase(it); 545 if (c == 0)break; 546 } 547 return c; 548 } 549 550 int upd(int l, int r, int p) { 551 int ans = 0, lst, lvl; 552 map<int, int>::iterator it; 553 access(l); 554 access(r); 555 lst = l; 556 lvl = sg[l]; 557 while (1) { 558 it = sg.upper_bound(l); 559 ans += chkmap((*it).first - lst, lvl); 560 lst = (*it).first; 561 lvl = (*it).second; 562 if ((*it).first == r)break; 563 sg.erase(it); 564 } 565 sg[l] = p; 566 mp[p] += r - l - ans; 567 return ans; 568 } 569 570 int main() { 571 ios::sync_with_stdio(false), cin.tie(0); 572 int T, n, m, q, i, u, v, p; 573 long long ans; 574 for (cin >> T; T > 0; T--) { 575 cin >> n >> m >> q; 576 for (i = 0; i < n - 1; i++) { 577 cin >> u >> v; 578 line[u - 1].push_back(v - 1); 579 line[v - 1].push_back(u - 1); 580 } 581 dep[0] = 0; 582 dfs1(0, -1); 583 cdfn = 0; 584 tp[0] = 0; 585 dfs2(0, -1); 586 sg[0] = -1; 587 sg[n] = -1; 588 for (i = 0; i < m; i++) { 589 cin >> p; 590 p--; 591 access(dfn[p] + 1); 592 sg[dfn[p]] = 0; 593 } 594 mp[0] = m; 595 ans = 0; 596 for (i = 1; i <= q; i++) { 597 u = p; 598 cin >> p; 599 p--; 600 p = (p + ans) % n; 601 v = p; 602 while (1) { 603 if (tp[u] == tp[v]) { 604 if (dep[v] > dep[u])swap(u, v); 605 ans += upd(dfn[v], dfn[u] + 1, i); 606 break; 607 } 608 if (dep[tp[v]] > dep[tp[u]])swap(u, v); 609 ans += upd(dfn[tp[u]], dfn[u] + 1, i); 610 u = fa[tp[u]]; 611 } 612 cout << ans << ' '; 613 } 614 cout << '\n'; 615 for (i = 0; i < n; i++)line[i].clear(); 616 mp.clear(); 617 sg.clear(); 618 } 619 return 0; 620 } 621 ``` 622 623 [2237I1 - DBFS Order (Easy Version)](/contest/2237/problem/I1) 624 625 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") & [Boboge](/profile/Boboge "Grandmaster Boboge") 626 627 **Tutorial** 628 629 Tutorial is loading... 630 631 [2237I2 - DBFS Order (Hard Version)](/contest/2237/problem/I2) 632 633 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") & [Boboge](/profile/Boboge "Grandmaster Boboge") 634 635 **Tutorial** 636 637 Tutorial is loading... 638 639 **Implementation** 640 641 ``` 642 #include<bits/stdc++.h> 643 644 using namespace std; 645 const long long mod = 1000000007; 646 vector<int> line[3000]; 647 string s; 648 long long dp[4][3000][3001], dpc[4][3000][3001], tdp[4][3001], tdpc[4][3001]; 649 int dep[3000], vis1[3000], vislink[3000]; 650 651 void merge(int u, int v, int pu, int pv, int pt) { 652 int i, j; 653 for (i = 0; i <= dep[u]; i++) { 654 for (j = 0; j <= dep[v]; j++) { 655 tdp[pt][max(i, j)] = (tdp[pt][max(i, j)] + dp[pu][u][i] * dp[pv][v][j]) % mod; 656 if (i <= j)tdpc[pt][j] = (tdpc[pt][j] + dp[pu][u][i] * dpc[pv][v][j]) % mod; 657 if (i > j)tdpc[pt][i] = (tdpc[pt][i] + dpc[pu][u][i] * dp[pv][v][j]) % mod; 658 } 659 } 660 } 661 662 void dfs(int t) { 663 vector<int>::iterator it; 664 int i, j, p, x, y, r0 = 0; 665 long long vl; 666 dp[0][t][0] = 1; 667 dep[t] = 0; 668 vis1[t] = 0; 669 vislink[t] = 0; 670 for (it = line[t].begin(); it != line[t].end(); it++) { 671 if (s[*it] == '0')r0++; 672 } 673 for (it = line[t].begin(); it != line[t].end(); it++) { 674 dfs(*it); 675 if (s[*it] == '0')r0--; 676 merge(t, *it, 0, 0, 0); 677 if (s[*it] == '1') { 678 merge(t, *it, 3, 1, 2); 679 merge(t, *it, 3, 1, 3); 680 } else { 681 merge(t, *it, 2, 1, 2); 682 merge(t, *it, 3, 1, 3); 683 } 684 if (vis1[t] == 0 && r0 == 0 && vislink[*it]) { 685 if (vislink[t] == 0) { 686 vislink[t] = 1; 687 for (i = 0; i <= dep[*it]; i++) { 688 tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod; 689 tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod; 690 tdp[3][i] = (tdp[3][i] + dp[3][*it][i]) % mod; 691 tdpc[3][i] = (tdpc[3][i] + dpc[3][*it][i]) % mod; 692 } 693 } else { 694 for (i = 0; i <= dep[*it]; i++) { 695 tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod; 696 tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod; 697 tdp[3][i] = (tdp[3][i] + dp[2][*it][i]) % mod; 698 tdpc[3][i] = (tdpc[3][i] + dpc[2][*it][i]) % mod; 699 if (s[*it] == '1') { 700 tdp[2][i] = (tdp[2][i] + dp[1][*it][i]) % mod; 701 tdpc[2][i] = (tdpc[2][i] + dpc[1][*it][i]) % mod; 702 tdp[3][i] = (tdp[3][i] + dp[1][*it][i]) % mod; 703 tdpc[3][i] = (tdpc[3][i] + dpc[1][*it][i]) % mod; 704 } 705 } 706 } 707 } 708 vis1[t] |= vis1[*it]; 709 dep[t] = max(dep[t], dep[*it]); 710 for (p = 0; p < 4; p++) { 711 for (i = 0; i <= dep[t]; i++) { 712 dp[p][t][i] = tdp[p][i]; 713 dpc[p][t][i] = tdpc[p][i]; 714 tdp[p][i] = 0; 715 tdpc[p][i] = 0; 716 } 717 } 718 } 719 if (s[t] == '0') { 720 dep[t]++; 721 return; 722 } 723 for (i = 0; i <= dep[t]; i++) { 724 tdp[0][i + 1] = (tdp[0][i + 1] + dp[0][t][i]) % mod; 725 tdpc[0][i + 1] = (tdpc[0][i + 1] + dpc[0][t][i]) % mod; 726 } 727 vl = 0; 728 for (i = 0; i <= dep[t]; i++) { 729 vl = (vl + dp[2][t][i]) % mod; 730 vl = (vl + mod - dpc[2][t][i]) % mod; 731 } 732 tdpc[0][1] = (tdpc[0][1] + vl) % mod; 733 dep[t]++; 734 vislink[t] = 1; 735 if (s[t] == '1') { 736 vis1[t] = 1; 737 for (i = 0; i <= dep[t]; i++) { 738 dp[0][t][i] = tdp[0][i]; 739 dpc[0][t][i] = tdpc[0][i]; 740 dp[1][t][i] = tdp[0][i]; 741 dpc[1][t][i] = tdpc[0][i]; 742 dp[2][t][i] = 0; 743 dpc[2][t][i] = 0; 744 dp[3][t][i] = 0; 745 dpc[3][t][i] = 0; 746 } 747 } else { 748 for (i = 0; i <= dep[t]; i++) { 749 dp[0][t][i] = (dp[0][t][i] + tdp[0][i]) % mod; 750 dpc[0][t][i] = (dpc[0][t][i] + tdpc[0][i]) % mod; 751 dp[1][t][i] = tdp[0][i]; 752 dpc[1][t][i] = tdpc[0][i]; 753 dp[3][t][i] = dp[2][t][i]; 754 dpc[3][t][i] = dpc[2][t][i]; 755 dp[2][t][i] = (dp[2][t][i] + tdp[0][i]) % mod; 756 dpc[2][t][i] = (dpc[2][t][i] + tdpc[0][i]) % mod; 757 } 758 } 759 for (i = 0; i <= dep[t]; i++) { 760 tdp[0][i] = 0; 761 tdpc[0][i] = 0; 762 } 763 } 764 765 int main() { 766 ios::sync_with_stdio(false), cin.tie(0); 767 int T, n, i, j, p, c; 768 long long ans; 769 for (cin >> T; T > 0; T--) { 770 cin >> n >> s; 771 s = '1' + s; 772 for (i = 0; i < n; i++) { 773 cin >> c; 774 for (j = 0; j < c; j++) { 775 cin >> p; 776 line[i].push_back(p - 1); 777 } 778 } 779 for (p = 0; p < 4; p++) { 780 for (i = 0; i < n; i++) { 781 for (j = 0; j <= n; j++) { 782 dp[p][i][j] = 0; 783 dpc[p][i][j] = 0; 784 } 785 } 786 } 787 dfs(0); 788 ans = 0; 789 for (i = 0; i <= dep[0]; i++) { 790 ans = (ans + dp[0][0][i]) % mod; 791 ans = (ans + mod - dpc[0][0][i]) % mod; 792 } 793 cout << ans << '\n'; 794 for (i = 0; i < n; i++)line[i].clear(); 795 } 796 return 0; 797 } 798 ```