1768.md (24885B)
1 Source: https://codeforces.com/blog/entry/110901 2 3 Hope you liked the problems! 4 5 **(from thanhchauns2) Before the round starts** 6 7 This is my second contest on Codeforces, inspiring coordination has been done for the last several months, cannot wait until the third round is released! 8 9 **Testers' predictions** 10 11 | Tester | A | B | C | D | E | F | 12 | --- | --- | --- | --- | --- | --- | --- | 13 | [xiaoziya](/profile/xiaoziya "International Grandmaster xiaoziya") | 900 | 1000 | 1400 | 1800 | 2100 | 3000 | 14 | [feecle6418](/profile/feecle6418 "Grandmaster feecle6418") | 900 | 1200 | 1400 | 1700 | 2200 | 2900 | 15 | [cadmiumky](/profile/cadmiumky "Candidate Master cadmiumky") | 800 | 1100 | 1550 | 1900 | 2200 | - | 16 | [6aren](/profile/6aren "Grandmaster 6aren") | 800 | 1200 | - | 2000 | 2200 | - | 17 | [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Grandmaster neko_nyaaaaaaaaaaaaaaaaa") | 800 | - | - | 2100 | 2400 | 3000 | 18 | [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") | 800 | 1100 | 1550 | 1800 | 2100 | 2550 | 19 20 **Some moments in the rating section** 21 22 **From neko_nyaaaaaaaaaaaaaaaaa** 23 24  25 26 **From hoangquan05112002** 27 28  29 30 **From _Astraea_** 31 32  33 34 **From Valenz** 35 36  37 38 **From TrendBattles** 39 40  41 42 **Some comments from testers and authors** 43 44 **From hoangquan05112002** 45 46  47 48 **From cadmiumky** 49 50  51 52 **From shiwei** 53 54  55 56 **From DMCS and DeMen100ns** 57 58  59 60 **tfg discussing problem F** 61 62    63 64 **From feecle6418** 65 66  67 68 **tibinyte and fextivity about problem A** 69 70  71 72 **neko_nyaa and errorgorn about problem A** 73 74  75 76 **From hoangquan05112002 again** 77 78  79 80 **From darkkcyan** 81 82  83 84 **From QuangBuiCP** 85 86  87 88 **From tibinyte, the Russian sentence is `use English please`** 89 90  91 92 **From errorgorn** 93 94  95 96 **From SPyofgame** 97 98  99 100 [1768A - Greatest Convex](/contest/1768/problem/A "Codeforces Round 842 (Div. 2)") 101 102 Author: [thanhchauns2](/profile/thanhchauns2 "Candidate Master thanhchauns2") 103 104 **Hints** 105 106 **Hint 1** 107 108 Try to brute force for $k \lt 50$. Do you see anything suspicious? 109 110 **Hint 2** 111 112 Now try to brute force from $k - 1$ to $0$ for large numbers. 113 114 **Tutorial** 115 116 ### [1768A- Greatest Convex](https://codeforces.com/contest/1768/problem/A) 117 118 Is $x = k - 1$ always suitable? 119 120 The answer is yes, as $x! + (x - 1)! = (x - 1)! \times (x + 1) = ((k - 1) - 1)! \times ((k - 1) + 1) = (k - 2)! \times (k)$, which is clearly a multiple of $k$. 121 122 Therefore, $x = k - 1$ is the answer. 123 124 Time complexity: $\mathcal{O}(1)$ 125 126 **Solution** 127 128 ``` 129 answer = [print(int(input()) - 1) for testcase in range(int(input()))] 130 ``` 131 132 **Feedback** 133 134 * Good problem 135 * Average problem 136 * Bad problem 137 138 [1768B - Quick Sort](/contest/1768/problem/B "Codeforces Round 842 (Div. 2)") 139 140 Author: [Vladithur](/profile/Vladithur "Master Vladithur") Preparation: [Vladithur](/profile/Vladithur "Master Vladithur") and [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000") 141 142 **Hints** 143 144 **Hint 1** 145 146 Try to have the last $k + 1$ numbers sorted. 147 148 **Hint 2** 149 150 Fix some set of numbers (not necessary sorted) of size $w$ and don't choose them in the operation. Try to have the last $n - w$ numbers sorted. 151 152 **Hint 3** 153 154 Fix the set of numbers $1,2,3,\ldots$ 155 156 **Tutorial** 157 158 Tutorial is loading... 159 160 **Solution** 161 162 ``` 163 #include <bits/stdc++.h> 164 165 #define all(x) (x).begin(), (x).end() 166 #define allr(x) (x).rbegin(), (x).rend() 167 #define gsize(x) (int)((x).size()) 168 169 const char nl = '\n'; 170 typedef long long ll; 171 typedef long double ld; 172 173 using namespace std; 174 175 void solve() { 176 int n, k; 177 cin >> n >> k; 178 vector<int> p(n); 179 for (int i = 0; i < n; i++) cin >> p[i]; 180 181 int c_v = 1; 182 for (int i = 0; i < n; i++) { 183 if (p[i] == c_v) c_v++; 184 } 185 186 cout << (n - c_v + k) / k << nl; 187 } 188 189 int main() { 190 ios::sync_with_stdio(0); cin.tie(0); 191 192 int T; 193 cin >> T; 194 while (T--) solve(); 195 } 196 ``` 197 198 **Feedback** 199 200 * Good problem 201 * Average problem 202 * Bad problem 203 204 [1768C - Elemental Decompress](/contest/1768/problem/C "Codeforces Round 842 (Div. 2)") 205 206 Author: [thanhchauns2](/profile/thanhchauns2 "Candidate Master thanhchauns2") 207 208 **Hints** 209 210 **Hint 1** 211 212 How many times a unique number can appear in the array $a$? 213 214 **Hint 2** 215 216 Can there be two numbers $1$ in $a$? What is the conclusion? 217 218 **Hint 3** 219 220 If you sort the array, which rules should the new array satisfy? Given the array $[1,2,2 ]$, is there any answer for this case? 221 222 **Hint 4** 223 224 Which element should you construct first? 225 226 **Tutorial** 227 228 ### [1768C- Elemental Decompress](https://codeforces.com/contest/1768/problem/C) 229 230 Two cases produce no answers: 231 232 * One element appears more than twice in $a$. 233 * After sorting, there is some index that $a[i] \lt i$ ($1$-indexed). 234 235 **Proof** 236 237 Consider there is some index that $a[i] \lt i$, then both $p[i] \lt i$ and $q[i] \lt i$ must satisfy. This is also true for the first $i - 1$ index, so the numbers that are smaller than $i$ in both $p$ and $q$ are $(i - 1) \times 2 + 2 = i * 2$. This is a contradiction. 238 239 Otherwise, solutions always exist. One method is to constructively attach each element in $a$ to $p$ or $q$: 240 241 * Traverse from the biggest element to the smallest in $a$, if that number haven't appeared in $p$ then attach it to $p$, otherwise attach it to $q$. 242 * Traverse from the biggest element to the smallest in $a$ again, if we attached it to $p$, find the biggest number that did not appear in $q$ and attach to $q$, vice versa. 243 244 A naive solution requires the $O(n^2)$ method to solve. We can reduce to $O(n \log n)$ by sorting elements in $a$ as pairs `<element, index>`. 245 246 Time complexity: $\mathcal{O}(n \log(n))$ 247 248 **Solution** 249 250 ``` 251 #include <bits/stdc++.h> 252 253 using namespace std; 254 255 const int N = 200005; 256 int n; 257 int a[N], b[N], c[N], ra[N], rb[N]; 258 259 void out() 260 { 261 for (int i = 0; i < n; i++) 262 { 263 cout << a[i] << ' '; 264 } 265 cout << '\n'; 266 267 for (int i = 0; i < n; i++) 268 { 269 cout << b[i] << ' '; 270 } 271 cout << '\n'; 272 } 273 274 void solve() 275 { 276 cin >> n; 277 vector<pair<int, int> > V; 278 for (int i = 0; i < n; i++) 279 { 280 cin >> c[i]; 281 a[i] = b[i] = 0; 282 ra[i + 1] = rb[i + 1] = 1; 283 V.push_back(make_pair(c[i], i)); 284 } 285 sort(V.rbegin(), V.rend()); 286 287 for (int i = 0; i < n; i++) 288 { 289 int k = V[i].second; 290 if (ra[c[k]] == 1) a[k] = c[k], ra[c[k]]--; 291 else b[k] = c[k], rb[c[k]]--; 292 } 293 294 int r1 = n, r2 = n; 295 for (int i = 0; i < n; i++) 296 { 297 int k = V[i].second; 298 if (a[k] == 0) 299 { 300 while (ra[r1] == 0) r1--; 301 ra[r1]--; 302 if (r1 > b[k]) 303 { 304 cout << "NO" << '\n'; 305 return; 306 } 307 a[k] = r1--; 308 } 309 else 310 { 311 while (rb[r2] == 0) r2--; 312 rb[r2]--; 313 if (r2 > a[k]) 314 { 315 cout << "NO" << '\n'; 316 return; 317 } 318 b[k] = r2--; 319 } 320 } 321 for (int i = 1; i <= n; i++) 322 { 323 if (ra[i] != 0 || rb[i] != 0) 324 { 325 cout << "NO" << '\n'; 326 return; 327 } 328 } 329 cout << "YES" << '\n'; 330 out(); 331 } 332 333 int main(int argc, char* argv[]) 334 { 335 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 336 int t; 337 cin >> t; 338 while(t--) 339 solve(); 340 } 341 ``` 342 343 **Yet another better solution** 344 345 There is actually a $O(n)$ solution to this problem. 346 347 **Fresh meme from SPyofgame to the intended solution of the author** 348 349  350 351 **Step 1** 352 353 If there are at least $k \gt 3$ positions $i_1, i_2, \ldots, i_k$ that $a[i_1] = a[i_2] = \ldots = a[i_k]$ then there is no solution. 354 355 **Proof** 356 357 Since we need the condition $a[i] = max(p[i], q[i])$, hence $p[i] = a[i]$ or/and $q[i] = a[i]$. 358 359 If there are already $p[i_1] = a[i_1]$ and $q[i_2] = a[i_2]$ then we don't have another number equal to $a[i_k]$ because $p[]$ and $q[]$ are two permutations (each number must appear exactly **once**). 360 361 **Approach** 362 363 ``` 364 /// Storing position of each a[i] 365 vector<vector<int> > b(n + 1); 366 for (int i = 1; i <= n; ++i) { 367 b[a[i]].push_back(i); 368 369 /// max(p[i], q[i]) = a[i] so either p[i] = a[i] or/and q[i] = a[i] 370 /// so if the number appear the third time or more, then "NO" 371 if (b[a[i]].size() >= 3) { 372 cout << "NO\n"; 373 return 0; 374 } 375 } 376 ``` 377 378 **Step 2** 379 380 Since we have the 381 382 Unable to parse markup [type=CF_MATHJAX] 383 384 function, we need to use the larger value firsts. 385 386 **Proof** 387 388 If we iterate from the smallest value to the top, there will be scenarios where all the remaining positions $i$ will result in $max(p[i], q[i]) \geq a[i]$ because you don't have enough smaller integers. 389 390 **Approach** 391 392 So for each $x = n \rightarrow 1$ (iterating from the largest element to the smallest element), we check for each position $i$ that $a_i = x$, then assign $p[i] := a[i]$ if $a[i]$ didn't appear in permutation $p[]$, otherwise assign $q[i] := a[i]$. 393 394 ``` 395 /// Initialize permutation p[1..n], q[1..n] 396 vector<int> p(n + 1, -1), q(n + 1, -1); 397 398 /// Initialize permutation position, fp[p[i]] = i, fq[q[i]] = i 399 vector<int> fp(n + 1, -1), fq(n + 1, -1); 400 for (int x = n; x >= 1; --x) { 401 for (int i : b[x]) { 402 /// Because of max(), we must save up the smaller value 403 /// So we assign p[i] or q[i] by x, one by one from x large -> small 404 if (fp[x] == -1) p[fp[x] = i] = x; 405 else if (fq[x] == -1) q[fq[x] = i] = x; 406 } 407 } 408 ``` 409 410 **Step 3** 411 412 We fill the remaining integers that wasn't used, from the largest to the smallest. 413 414 **Approach** 415 416 We use $vp$ as the largest integer not used in permutation $p[1..n]$. 417 418 We use $vq$ as the largest integer not used in permutation $q[1..n]$. 419 420 Then for each of the value $x = n \rightarrow 1$, we assign to $p[i], q[i]$ that was not used. 421 422 ``` 423 for (int x = n, vp = n, vq = n; x >= 1; --x) { 424 for (int i : b[x]) { 425 /// Assign the remaining integers 426 while (fp[vp] != -1) --vp; 427 while (fq[vq] != -1) --vq; 428 if (p[i] == -1 && vp > 0) p[fp[vp] = i] = vp; 429 if (q[i] == -1 && vq > 0) q[fq[vq] = i] = vq; 430 } 431 } 432 ``` 433 434 **Step 4** 435 436 Check if the permutation $p[]$ and $q[]$ satisfied the solution, if it didnt then output "NO", otherwise output "YES" and the two permutations: $p[1..n]$ and $q[1..n]$. 437 438 **Approach** 439 440 Just iterate through each element as normal. 441 442 ``` 443 for (int i = 1; i <= n; ++i) { 444 if (max(p[i], q[i]) != a[i]) { 445 /// Statement condition is not satisfied 446 cout << "NO\n"; 447 return 0; 448 } 449 } 450 451 /// Output the answer 452 cout << "YES\n"; 453 for (int i = 1; i <= n; ++i) cout << p[i] << " "; cout << "\n"; 454 for (int i = 1; i <= n; ++i) cout << q[i] << " "; cout << "\n"; 455 ``` 456 457 **Bonus** 458 459 There is also another way that you can skip testing if $max(p[i], q[i]) = a[i])$ is correct. 460 461 But the proof is a bit harder to understand, so I prefer using this code instead. 462 463 **Full Code** 464 465 ``` 466 #include <iostream> 467 #include <vector> 468 469 using namespace std; 470 471 int query() 472 { 473 /// Input number of element 474 int n; 475 cin >> n; 476 477 /// Input the array a[1..n] 478 vector<int> a(n + 1); 479 for (int i = 1; i <= n; ++i) 480 cin >> a[i]; 481 482 /// Storing position of each a[i] 483 vector<vector<int> > b(n + 1); 484 for (int i = 1; i <= n; ++i) { 485 b[a[i]].push_back(i); 486 487 /// max(p[i], q[i]) = a[i] so either p[i] = a[i] or/and q[i] = a[i] 488 /// so if the number appear the third time or more, then "NO" 489 if (b[a[i]].size() >= 3) { 490 cout << "NO\n"; 491 return 0; 492 } 493 } 494 495 /// Initialize permutation p[1..n], q[1..n] 496 vector<int> p(n + 1, -1), q(n + 1, -1); 497 498 /// Initialize permutation position, fp[p[i]] = i, fq[q[i]] = i 499 vector<int> fp(n + 1, -1), fq(n + 1, -1); 500 for (int x = n; x >= 1; --x) { 501 for (int i : b[x]) { 502 /// Because of max(), we must save up the larger value 503 /// So we assign p[i] or q[i] by x, one by one from x large -> small 504 if (fp[x] == -1) p[fp[x] = i] = x; 505 else if (fq[x] == -1) q[fq[x] = i] = x; 506 } 507 } 508 509 for (int x = n, vp = n, vq = n; x >= 1; --x) { 510 for (int i : b[x]) { 511 /// Assign the remaining integers 512 while (fp[vp] != -1) --vp; 513 while (fq[vq] != -1) --vq; 514 if (p[i] == -1 && vp > 0) p[fp[vp] = i] = vp; 515 if (q[i] == -1 && vq > 0) q[fq[vq] = i] = vq; 516 } 517 } 518 519 for (int i = 1; i <= n; ++i) { 520 if (max(p[i], q[i]) != a[i]) { 521 /// Statement condition is not satisfied 522 cout << "NO\n"; 523 return 0; 524 } 525 } 526 527 /// Output the answer 528 cout << "YES\n"; 529 for (int i = 1; i <= n; ++i) cout << p[i] << " "; cout << "\n"; 530 for (int i = 1; i <= n; ++i) cout << q[i] << " "; cout << "\n"; 531 return 0; 532 } 533 534 signed main() 535 { 536 ios::sync_with_stdio(NULL); 537 cin.tie(NULL); 538 539 int q = 1; /// If there is no multiquery 540 cin >> q; /// then comment this 541 542 while (q-->0) 543 { 544 /// For each query 545 query(); 546 547 } 548 549 return 0; 550 } 551 ``` 552 553 **Feedback** 554 555 * I reached $O(n \log n)$ solution. 556 * I reached $O(n)$ solution. 557 558 **Feedback** 559 560 * Good problem 561 * Average problem 562 * Bad problem 563 564 [1768D - Lucky Permutation](/contest/1768/problem/D "Codeforces Round 842 (Div. 2)") 565 566 Author: [Vladithur](/profile/Vladithur "Master Vladithur") Preparation: [Vladithur](/profile/Vladithur "Master Vladithur") and [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000") 567 568 **Hints** 569 570 **Hint 1** 571 572 There are $n - 1$ permutations of length $n$ that have exactly one inversion in them. 573 574 **Hint 2** 575 576 This problem is similar to finding the minimum number of swaps needed to sort a permutation. 577 578 **Hint 3** 579 580 Try looking at the permutation like a graph. 581 582 **Hint 4** 583 584 Try to find the number of cycles in each of the $n - 1$ graphs. 585 586 **Tutorial** 587 588 Tutorial is loading... 589 590 **Solution** 591 592 ``` 593 #include <bits/stdc++.h> 594 595 #define all(x) (x).begin(), (x).end() 596 #define allr(x) (x).rbegin(), (x).rend() 597 #define gsize(x) (int)((x).size()) 598 599 const char nl = '\n'; 600 typedef long long ll; 601 typedef long double ld; 602 603 using namespace std; 604 605 void solve() { 606 int n; 607 cin >> n; 608 vector<int> p(n); 609 for (int i = 0; i < n; i++) { 610 cin >> p[i]; p[i]--; 611 } 612 613 int ind = 1, ans = 0; 614 vector<int> comp(n, 0); 615 for (int i = 0; i < n; i++) { 616 if (comp[i]) continue; 617 { 618 int v = i; 619 while (comp[v] == 0) { 620 comp[v] = ind; 621 v = p[v]; 622 ans++; 623 } 624 625 ind++; ans--; 626 } 627 } 628 629 for (int i = 0; i < n - 1; i++) { 630 if (comp[i] == comp[i + 1]) { 631 cout << ans - 1 << nl; 632 return; 633 } 634 } 635 cout << ans + 1 << nl; 636 } 637 638 int main() { 639 ios::sync_with_stdio(0); cin.tie(0); 640 641 int T; 642 cin >> T; 643 while (T--) solve(); 644 } 645 ``` 646 647 **Feedback** 648 649 * Good problem 650 * Average problem 651 * Bad problem 652 653 [1768E - Partial Sorting](/contest/1768/problem/E "Codeforces Round 842 (Div. 2)") 654 655 Author: [thanhchauns2](/profile/thanhchauns2 "Candidate Master thanhchauns2") 656 657 **Hints** 658 659 **Hint 1** 660 661 Given a fixed permutation, how many operations do we need to sort it? 662 663 **Hint 2** 664 665 Keep in mind there is one already sorted permutation that doesn't need to be sorted. 666 667 **Hint 3** 668 669 What if there is exactly $1$ number in the range $[n + 1, 2n]$ that appears in the first $n$ numbers? 670 671 **Hint 4** 672 673 This is not really a hint, fft solutions exist, but we made sure most of them cannot pass. 674 675 **Tutorial** 676 677 ### [1768E- Partial Sorting](https://codeforces.com/contest/1768/problem/E) 678 679 We need at most $3$ operations to sort the permutation: $1 - \gt 2 - \gt 1$ 680 681 * For $f(p) = 0$, there is only one case: the initially sorted permutation. 682 683 **Calculate** 684 685 `return (38912738912739811 & 1)` 686 687 * For $f(p) \leq 1$, this scenario appears when the first $n$ numbers or the last $n$ numbers are in the right places. 688 689 **Calculate** 690 691 Both cases have $n$ fixed positions, so there will be $(2n!)$ permutations in each case. 692 693 Intersection: since both cases share the $n$ middle elements, $(n!)$ permutation will appear in both cases. 694 695 So there will be $2 \times (2n!) - (n!)$ such permutations. 696 697 * For $f(p) \leq 2$, this scenario appears when the smallest $n$ elements' positions are in range $[1, 2n]$, or the largest $n$ numbers' positions are in range $[n + 1, 3n]$. 698 699 **Calculate** 700 701 If the smallest $n$ elements are all in position from $1$ to $2n$, then: 702 703 * There are $C_{2n}^{n}$ ways to choose $n$ positions for these numbers. 704 * For each way to choose these positions, there are $n!$ ways to choose the position for the smallest $n$ numbers, and $2n!$ ways for the rest. 705 * The total number of valid permuations are: $C_{2n}^{n} \times n! \times 2n!$ 706 707 If the largest $n$ elements are all in position from $n + 1$ to $3n$, we do the same calculation. 708 709 Intersection: intersection appears when the first $n$ numbers are all in range $[1, 2n]$ and the last $n$ numbers are all in range $[n + 1, 3n]$. 710 711 Let `intersection = 0` 712 713 **Sketch and calculation in details** 714 715 Let's talk about the numbers in range $[n + 1, 2n]$. There are $n$ such numbers. 716 717 . Imagine there are EXACTLY $i = 0$ numbers in this range that appear in the first $n$ numbers. So: 718 719 * In the first $n$ numbers there are $n$ numbers in range $[1, n]$. There are $C_{n}^{n - 0} \times n!$ cases. 720 * In the first $n$ numbers there are $0$ numbers in range $[n + 1, 2n]$. There are $C_{n}^{0} \times n!$ cases. 721 * In the last $n$ numbers there are $n$ numbers in range $[n + 1, 3n]$, we have used $0$ numbers for the first n numbers. There are $C_{2n - 0}^{n} \times n!$ cases. 722 723 Then we have: `intersection +=` $C_{n}^{n - 0} \times C_{n}^{0} \times C_{2n - 0}^{n} \times n! \times n! \times n!$ 724 725 After convert $0$ to $i$, we have `intersection +=` $C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$ 726 727 How about there is EXACTLY $i = 1$ number in range $[n + 1, 2n]$ appearing in the first $n$ numbers? 728 729 * In the first $n$ numbers there are $n - 1$ numbers in range $[1, n]$. There are $C_{n}^{n - 1} \times n!$ cases. 730 * In the first $n$ numbers there are $1$ numbers in range $[n + 1, 2n]$. There are $C_{n}^{1} \times n!$ cases. 731 * In the last $n$ numbers there are $n$ numbers in range $[n + 1, 3n]$, we have used $1$ numbers for the first $n$ numbers. There are $C_{2n - 1}^{n} \times n!$ cases. 732 733 Then we have: `intersection +=` $C_{n}^{n - 1} \times C_{n}^{1} \times C_{2n - 1}^{n} \times n! \times n! \times n!$ 734 735 After convert $1$ to $i$, we have `intersection +=` $C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$ 736 737 We do the same thing with remaining cases, all the way up to $i = n$. 738 739 The number of intersections will be equal to: $ \sum_{i = 0}^{n} C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n! $ 740 741 So, the answer will be $2 \times C_{2n}^{n} \times n! \times 2n! - \sum_{i = 0}^{n} C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$ 742 743 * For $f(p) \leq 3$, it will be the count of all valid permutations. 744 745 **Calculate** 746 747 `return __factorial(n * __number_of_sides_of_a_triangle)` 748 749 Time complexity: $\mathcal{O}(n)$ 750 751 **Solution** 752 753 ``` 754 #include <bits/stdc++.h> 755 756 using namespace std; 757 758 long long n, M; 759 760 long long frac[3000005], inv[3000005]; 761 762 long long powermod(long long a, long long b, long long m) 763 { 764 if (b == 0) return 1; 765 unsigned long long k = powermod(a, b / 2, m); 766 k = k * k; 767 k %= m; 768 if (b & 1) k = (k * a) % m; 769 return k; 770 } 771 772 void Ready() 773 { 774 frac[0] = 1; 775 inv[0] = 1; 776 for (int i = 1; i <= 3000000; i++) 777 { 778 frac[i] = (frac[i - 1] * i) % M; 779 } 780 781 inv[3000000] = powermod(frac[3000000], M - 2, M); 782 783 for (int i = 3000000; i > 0; i--) 784 { 785 inv[i - 1] = (inv[i] * i) % M; 786 } 787 } 788 789 long long C(long long n, long long k) 790 { 791 return ((frac[n] * inv[k]) % M * inv[n - k]) % M; 792 } 793 794 int main() 795 { 796 cin >> n >> M; 797 Ready(); 798 long long ans[4]{}; 799 800 // X = 0 801 802 ans[0] = 1; 803 804 // X = 1 805 806 ans[1] = 2 * frac[2 * n] - frac[n] - ans[0] + M + M; 807 ans[1] %= M; 808 809 // X = 2 810 811 ans[2] = frac[2 * n]; 812 ans[2] = ans[2] * C(2 *n, n) % M; 813 ans[2] = ans[2] * frac[n] % M; 814 ans[2] = ans[2] * 2 % M; 815 816 for (int i = 0; i <= n; i++) 817 { 818 int sub = C(n, i); 819 sub = sub * C(n, n - i) % M; 820 sub = sub * C(2 * n - i, n) % M; 821 sub = sub * frac[n] % M; 822 sub = sub * frac[n] % M; 823 sub = sub * frac[n] % M; 824 ans[2] = (ans[2] - sub + M) % M; 825 } 826 ans[2] = (ans[2] - ans[1] + M) % M; 827 ans[2] = (ans[2] - ans[0] + M) % M; 828 829 // X = 3 830 831 ans[3] = frac[3 * n]; 832 ans[3] = (ans[3] - ans[2] + M) % M; 833 ans[3] = (ans[3] - ans[1] + M) % M; 834 ans[3] = (ans[3] - ans[0] + M) % M; 835 836 long long answer = ans[1] + 2 * ans[2] + 3 * ans[3]; 837 answer %= M; 838 839 cout << answer << endl; 840 } 841 ``` 842 843 **Feedback** 844 845 * Good problem 846 * Average problem 847 * Bad problem 848 849 [1768F - Wonderful Jump](/contest/1768/problem/F "Codeforces Round 842 (Div. 2)") 850 851 Author: [Vladithur](/profile/Vladithur "Master Vladithur") Preparation: [Vladithur](/profile/Vladithur "Master Vladithur") and [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000") 852 853 **Hints** 854 855 **Hint 0** 856 857 Use dynamic programming. 858 859 **Hint 1** 860 861 $a_i \le n$ 862 863 **Hint 2** 864 865 Compare $\min(a_i \ldots a_j) \cdot (j - i)^2$ with $n \cdot (j - i)$. 866 867 **Hint 3** 868 869 Compare $\min(a_i \ldots a_j) \cdot (j - i)^2$ with $\min(a_i \ldots a_k) \cdot (k - i)^2 + \min(a_k \ldots a_j) \cdot (j - k)^2$ for some $i \lt k \lt j$. 870 871 **Hint 4** 872 873 Two cases: $\min(a_i \ldots a_j) \ge \sqrt{n}$ and $\min(a_i \ldots a_j) \lt \sqrt{n}$. 874 875 **Hint 5** 876 877 Split $\min(a_i \ldots a_j) \lt \sqrt{n}$ into two more cases: $\min(a_i \ldots a_j) = a_i$ and $\min(a_i \ldots a_j) = a_j$. 878 879 **Tutorial** 880 881 Tutorial is loading... 882 883 **Solution** 884 885 ``` 886 #include <bits/stdc++.h> 887 888 #define all(x) (x).begin(), (x).end() 889 #define allr(x) (x).rbegin(), (x).rend() 890 #define gsize(x) (int)((x).size()) 891 892 const char nl = '\n'; 893 typedef long long ll; 894 typedef long double ld; 895 896 using namespace std; 897 898 const int K = 650; 899 900 int main() { 901 ios::sync_with_stdio(0); cin.tie(0); 902 903 int n; 904 cin >> n; 905 vector<ll> a(n); 906 for (int i = 0; i < n; i++) cin >> a[i]; 907 908 vector<ll> dp(n, 1e18); 909 dp[0] = 0; 910 911 vector<int> st = {0}; 912 for (int i = 1; i < n; i++) { 913 // Case 1 914 { 915 ll mi = a[i]; 916 for (int j = i - 1; j >= max(0, i - K); j--) { 917 mi = min(mi, a[j]); 918 dp[i] = min(dp[i], dp[j] + mi * (i - j) * (i - j)); 919 } 920 } 921 922 // Case 2 923 if (a[i] <= K) { 924 for (int j = i - 1; j >= 0; j--) { 925 dp[i] = min(dp[i], dp[j] + a[i] * (i - j) * (i - j)); 926 if (a[j] <= a[i]) break; 927 } 928 } 929 930 // Case 3 931 { 932 for (int j: st) { 933 dp[i] = min(dp[i], dp[j] + a[j] * (i - j) * (i - j)); 934 } 935 936 if (a[i] <= K) { 937 while (!st.empty() && a[st.back()] >= a[i]) { 938 st.pop_back(); 939 } 940 st.push_back(i); 941 } 942 } 943 } 944 945 for (int i = 0; i < n; i++) cout << dp[i] << ' '; 946 cout << endl; 947 } 948 ``` 949 950 **Shorter solution (tfg)** 951 952 ``` 953 #include <iostream> 954 #include <vector> 955 #include <chrono> 956 #include <random> 957 #include <cassert> 958 959 std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); 960 961 int main() { 962 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); 963 int n; 964 std::cin >> n; 965 std::vector<int> a(n); 966 for(int i = 0; i < n; i++) { 967 std::cin >> a[i]; 968 } 969 std::vector<long long> dp(n, 1e18); 970 dp[0] = 0; 971 for(int i = 0; i < n; i++) { 972 int dist = n / a[i] + 1; 973 // take from behind 974 for(int j = i-1; j >= 0 && i-j <= dist; j--) { 975 dp[i] = std::min(dp[i], dp[j] + (long long) a[i] * (i - j) * (i - j)); 976 if(a[j] <= a[i]) break; 977 } 978 // propagate forward 979 for(int j = i+1; j < n && j-i <= dist; j++) { 980 dp[j] = std::min(dp[j], dp[i] + (long long) a[i] * (i - j) * (i - j)); 981 if(a[j] <= a[i]) break; 982 } 983 std::cout << dp[i] << (i + 1 == n ? '\n' : ' '); 984 } 985 } 986 ``` 987 988 **Feedback** 989 990 * Good problem 991 * Average problem 992 * Bad problem