2039.md (36945B)
1 Source: https://codeforces.com/blog/entry/136523 2 3 Thanks for participating in the contest [](https://emoji.gg/emoji/8771_blobheart). We hope you liked the problems. We would love to hear your feedback in the comments. 4 5 If you find anything wrong in the editorial which is more likely to happen because we have written a rather long editorial to make you understand the solutions better, then comment below. 6 7 We also tried to write the thought process of how you can come up with the solution for the easier problems. The approach I followed is similar to what the current AI agents do. They first generate some thoughts, then do some actions, then gather observations, and repeat the process until they find the solution. Hope you will like this approach. 8 9 Also, don't forget to upvote the editorial. See you in the next contest! 10 11 Also, **please rate the problems after checking the editorial**. Because otherwise you might have solved it in a very cumbersome way that you will end up hating the problem. 12 13 **How did you find the contest?** 14 15 * Great: 16 * Good: 17 * Average: 18 * Bad: 19 * Trash: 20 21 **Which problem is your most favourite?** 22 23 * A: 24 * B: 25 * C1: 26 * C2: 27 * D: 28 * E: 29 * F1: 30 * F2: 31 * G: 32 * H1: 33 * H2: 34 35 **Which problem you hate the most?** 36 37 * A: 38 * B: 39 * C1: 40 * C2: 41 * D: 42 * E: 43 * F1: 44 * F2: 45 * G: 46 * H1: 47 * H2: 48 49 Also, huge props to [redpanda](/profile/redpanda "Expert redpanda") for creating **awesome manim video editorials** for problems A to D. Check it out here: <https://www.youtube.com/watch?v=elRvvUbk1J4> 50 51 [2039A - Shohag Loves Mod](/contest/2039/problem/A) 52 53 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Code** 60 61 ``` 62 #include<bits/stdc++.h> 63 using namespace std; 64 65 const int N = 3e5 + 9; 66 using ll = long long; 67 68 void solve() { 69 int n; cin >> n; 70 for (int i = 1; i <= n; i++) { 71 cout << 2 * i - 1 << ' '; 72 } 73 cout << '\n'; 74 } 75 76 int32_t main() { 77 ios_base::sync_with_stdio(0); 78 cin.tie(0); 79 int t = 1; 80 cin >> t; 81 while (t--) { 82 solve(); 83 } 84 return 0; 85 } 86 ``` 87 88 **Rate the Problem** 89 90 * Amazing problem: 91 * Good problem: 92 * Average problem: 93 * Bad problem: 94 * Didn't solve: 95 96 [2039B - Shohag Loves Strings](/contest/2039/problem/B) 97 98 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 99 100 **Tutorial** 101 102 Tutorial is loading... 103 104 **Code** 105 106 ``` 107 #include<bits/stdc++.h> 108 using namespace std; 109 110 const int N = 3e5 + 9; 111 using ll = long long; 112 113 void solve() { 114 string s; cin >> s; 115 int n = s.size(); 116 for (int i = 0; i + 1 < n; i++) { 117 if (s[i] == s[i + 1]) { 118 cout << s.substr(i, 2) << '\n'; 119 return; 120 } 121 } 122 for (int i = 0; i + 2 < n; i++) { 123 if (s[i] != s[i + 1] and s[i] != s[i + 2] and s[i + 1] != s[i + 2]) { 124 cout << s.substr(i, 3) << '\n'; 125 return; 126 } 127 } 128 cout << -1 << '\n'; 129 } 130 131 int32_t main() { 132 ios_base::sync_with_stdio(0); 133 cin.tie(0); 134 int t = 1; 135 cin >> t; 136 while (t--) { 137 solve(); 138 } 139 return 0; 140 } 141 ``` 142 143 **Rate the Problem** 144 145 * Amazing problem: 146 * Good problem: 147 * Average problem: 148 * Bad problem: 149 * Didn't solve: 150 151 [2039C1 - Shohag Loves XOR (Easy Version)](/contest/2039/problem/C1) 152 153 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Code** 160 161 ``` 162 #include<bits/stdc++.h> 163 using namespace std; 164 165 using ll = long long; 166 167 void solve() { 168 int x; ll m; cin >> x >> m; 169 170 int ans = 0; 171 for (int y = 1; y <= min(2LL * x, m); y++) { 172 if (x != y and ((x % (x ^ y)) == 0 or (y % (x ^ y) == 0))) { 173 ++ans; 174 } 175 } 176 cout << ans << '\n'; 177 } 178 179 int32_t main() { 180 ios_base::sync_with_stdio(0); 181 cin.tie(0); 182 int t = 1; 183 cin >> t; 184 while (t--) { 185 solve(); 186 } 187 return 0; 188 } 189 ``` 190 191 **Rate the Problem** 192 193 * Amazing problem: 194 * Good problem: 195 * Average problem: 196 * Bad problem: 197 * Didn't solve: 198 199 [2039C2 - Shohag Loves XOR (Hard Version)](/contest/2039/problem/C2) 200 201 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 **Code** 208 209 ``` 210 #include<bits/stdc++.h> 211 using namespace std; 212 213 using ll = long long; 214 215 void solve() { 216 int x; ll m; cin >> x >> m; 217 218 // divisible by x 219 ll p = m - m % x; 220 ll ans = p / x - (x < p); 221 if ((x ^ p) >= 1 and (x ^ p) <= m) ++ans; 222 p += x; 223 if ((x ^ p) >= 1 and (x ^ p) <= m) ++ans; 224 225 // divisibly by y 226 for (int y = 1; y <= min(1LL * x, m); y++) { 227 ll cur = x ^ y; 228 if (cur % y == 0) { 229 ++ans; 230 } 231 } 232 233 // divisible by both 234 if (x <= m) { 235 --ans; 236 } 237 238 cout << ans << '\n'; 239 } 240 241 int32_t main() { 242 ios_base::sync_with_stdio(0); 243 cin.tie(0); 244 int t = 1; 245 cin >> t; 246 while (t--) { 247 solve(); 248 } 249 return 0; 250 } 251 ``` 252 253 **Rate the Problem** 254 255 * Amazing problem: 256 * Good problem: 257 * Average problem: 258 * Bad problem: 259 * Didn't solve: 260 261 [2039D - Shohag Loves GCD](/contest/2039/problem/D) 262 263 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 264 265 **Tutorial** 266 267 Tutorial is loading... 268 269 **Code (Solution 1)** 270 271 ``` 272 #include<bits/stdc++.h> 273 using namespace std; 274 275 const int N = 1e5 + 9; 276 int p[N]; 277 void solve() { 278 int n, m; cin >> n >> m; 279 vector<int> s(m + 1); 280 for (int i = 1; i <= m; i++) { 281 cin >> s[i]; 282 } 283 if (m < __lg(n) + 1) { 284 cout << -1 << '\n'; 285 return; 286 } 287 for (int i = 1; i <= n; i++) { 288 cout << s[m - p[i]] << ' '; 289 } 290 cout << '\n'; 291 } 292 293 int32_t main() { 294 ios_base::sync_with_stdio(0); 295 cin.tie(0); 296 for (int i = 2; i < N; i++) { 297 if (p[i]) continue; 298 for (int j = i; j < N; j += i) { 299 int x = j; 300 while (x % i == 0) x /= i, ++p[j]; 301 } 302 } 303 int t = 1; 304 cin >> t; 305 while (t--) { 306 solve(); 307 } 308 return 0; 309 } 310 ``` 311 312 **Code (Solution 2)** 313 314 ``` 315 #include<bits/stdc++.h> 316 using namespace std; 317 318 const int N = 1e5 + 9; 319 using ll = long long; 320 321 vector<int> d[N]; 322 void solve() { 323 int n, m; cin >> n >> m; 324 vector<int> s(m + 1); 325 for (int i = 1; i <= m; i++) { 326 cin >> s[i]; 327 } 328 vector<int> a(n + 1, -1); 329 for (int i = 1; i <= n; i++) { 330 set<int> banned; 331 for (int j: d[i]) { 332 banned.insert(a[j]); 333 } 334 for (int k = m; k >= 1; k--) { 335 if (banned.find(s[k]) == banned.end()) { 336 a[i] = s[k]; 337 break; 338 } 339 } 340 if (a[i] == -1) { 341 cout << -1 << '\n'; 342 return; 343 } 344 } 345 for (int i = 1; i <= n; i++) { 346 cout << a[i] << ' '; 347 } 348 cout << '\n'; 349 } 350 351 int32_t main() { 352 ios_base::sync_with_stdio(0); 353 cin.tie(0); 354 for (int i = 1; i < N; i++) { 355 for (int j = i + i; j < N; j += i) { 356 d[j].push_back(i); 357 } 358 } 359 int t = 1; 360 cin >> t; 361 while (t--) { 362 solve(); 363 } 364 return 0; 365 } 366 ``` 367 368 **Rate the Problem** 369 370 * Amazing problem: 371 * Good problem: 372 * Average problem: 373 * Bad problem: 374 * Didn't solve: 375 376 [2039E - Shohag Loves Inversions](/contest/2039/problem/E) 377 378 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 379 380 **Tutorial** 381 382 Tutorial is loading... 383 384 **Code** 385 386 ``` 387 #include<bits/stdc++.h> 388 using namespace std; 389 390 const int N = 1e6 + 9, mod = 998244353; 391 using ll = long long; 392 393 int dp[N]; // count of arrays that we can get if the current number of inversions is > max element of the array 394 void solve() { 395 int n; cin >> n; 396 int sum = 0; 397 for (int i = n; i >= 1; i--) { 398 dp[i] = (1LL * i * sum % mod + 1) % mod; 399 sum = (sum + dp[i]) % mod; 400 } 401 int ans = n - 1; // arrays having 0 and 1 inversions 402 for (int k = 3; k <= n; k++) { 403 int ways = (1LL * (k - 1) * (k - 2) / 2 - 1 + mod) % mod; // count of arrays achievable such that > 1 inversion count was inserted for the first time 404 ans += 1LL * ways * dp[k] % mod; 405 ans %= mod; 406 } 407 cout << ans << '\n'; 408 } 409 410 int32_t main() { 411 ios_base::sync_with_stdio(0); 412 cin.tie(0); 413 int t = 1; 414 cin >> t; 415 while (t--) { 416 solve(); 417 } 418 return 0; 419 } 420 ``` 421 422 **Code (by wyrqwq, without initial casework)** 423 424 ``` 425 #include <bits/stdc++.h> 426 427 #include <chrono> 428 std::mt19937 eng(std::chrono::steady_clock::now().time_since_epoch().count()); 429 int rnd(int l, int r) { return std::uniform_int_distribution<int>(l, r)(eng); } 430 431 namespace FastIO { 432 // char buf[1 << 21], *p1 = buf, *p2 = buf; 433 // #define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++) 434 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 435 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); } 436 template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); } 437 template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); } 438 // inline char rChar() { char ch = getchar(); while (!isalpha(ch)) ch = getchar(); return ch; } 439 }; using namespace FastIO; 440 441 using i32 = int32_t; 442 using u32 = uint32_t; 443 using u64 = uint64_t; 444 template <uint32_t MOD> struct mint { 445 static constexpr u32 get_r() { 446 u32 ret = MOD; 447 for (i32 i = 0; i < 4; ++i) ret *= 2 - MOD * ret; 448 return ret; 449 } 450 static constexpr u32 r = get_r(); 451 static constexpr u32 n2 = -u64(MOD) % MOD; 452 static_assert(r * MOD == 1, "invalid, r * MOD != 1"); 453 static_assert(MOD < (1 << 30), "invalid, MOD >= 2 ^ 30"); 454 static_assert((MOD & 1) == 1, "invalid, MOD % 2 == 0"); 455 u32 a; 456 constexpr mint() : a(0) {} 457 constexpr mint(const int64_t &b) : a(reduce(u64(b % MOD + MOD) * n2)){}; 458 static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * MOD) >> 32; } 459 constexpr mint &operator += (const mint &b) { if (i32(a += b.a - 2 * MOD) < 0) a += 2 * MOD; return *this; } 460 constexpr mint &operator -= (const mint &b) { if (i32(a -= b.a) < 0) a += 2 * MOD; return *this; } 461 constexpr mint &operator *= (const mint &b) { a = reduce(u64(a) * b.a); return *this; } 462 constexpr mint &operator /= (const mint &b) { *this *= b.inverse(); return *this; } 463 constexpr mint operator + (const mint &b) const { return mint(*this) += b; } 464 constexpr mint operator - (const mint &b) const { return mint(*this) -= b; } 465 constexpr mint operator * (const mint &b) const { return mint(*this) *= b; } 466 constexpr mint operator / (const mint &b) const { return mint(*this) /= b; } 467 constexpr bool operator == (const mint &b) const { return (a >= MOD ? a - MOD : a) == (b.a >= MOD ? b.a - MOD : b.a); } 468 constexpr bool operator != (const mint &b) const { return (a >= MOD ? a - MOD : a) != (b.a >= MOD ? b.a - MOD : b.a); } 469 constexpr mint operator-() const { return mint() - mint(*this); } 470 constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; } 471 constexpr mint inverse() const { return pow(MOD - 2); } 472 friend std::ostream &operator<< (std::ostream &os, const mint &b) { return os << b.get(); } 473 friend std::istream &operator>> (std::istream &is, mint &b) { int64_t t; is >> t; b = mint<MOD>(t); return (is); } 474 constexpr u32 get() const { u32 ret = reduce(a); return ret >= MOD ? ret - MOD : ret; } 475 static constexpr u32 get_MOD() { return MOD; } 476 explicit operator u32() const { return get(); } 477 }; using modint = mint<998244353>; 478 479 // Let's write some brute first 480 // dp[i][j] := current length is i, current number of inversions is j (not inserted) 481 // dp[i][j] -> dp[>= i + 1][[j + 1, j + i]] 482 // this is true for j >= 1, so let's do something when j = 0 483 // we can generate [0, (0 ... ), 1, 0] -> dp[>= 3][1] 484 // this is still kinda annoying because 1 > 1 does not hold, we process it till j >= 2 485 // [0, 0, ..., 0, 1, 0] -> [0, 0, ..., 0, 1, 0, 1, ..., 1] 486 // after that we insert an 1 before some numbers of 0 and we get dp[i][1] -> dp[>= i + 1][[j + 1, j + i - 1]] 487 // the answer is sum dp[i][j] for all 1 <= i <= n, j >= 1, plus 1 ([0, 0, 0 ... 1]) 488 // actually we care nothing 'bout, j so let's say f[i] = sum dp[i][j] 489 // (f[i] * i - 1) -> f[i + 1], f[i + 2], ..., f[n] 490 491 #define MAXN 1000001 492 modint f[MAXN]; 493 void solve() { 494 int n = read<int>(); modint ans = 1, pre = 2; 495 f[3] = 1; 496 for (int i = 4; i <= n; ++i) 497 f[i] = pre + modint(1), pre += f[i] * modint(i) - modint(1); 498 for (int i = 3; i <= n; ++i) ans += f[i]; 499 // f[3] : [0, 1, 0] 500 // f[4] : [0, 0, 1, 0] (+1), [0, 1, 1, 0], [1, 0, 1, 0] (dp[3][1] * 2) 501 print<int>(ans.get(), '\n'); 502 } 503 504 int main() { int T = read<int>(); while (T--) solve(); return 0; } 505 ``` 506 507 **Rate the Problem** 508 509 * Amazing problem: 510 * Good problem: 511 * Average problem: 512 * Bad problem: 513 * Didn't solve: 514 515 [2039F1 - Shohag Loves Counting (Easy Version)](/contest/2039/problem/F1) 516 517 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 518 519 **Tutorial** 520 521 Tutorial is loading... 522 523 **Code (by LipArcanjo)** 524 525 ``` 526 #include<bits/stdc++.h> 527 using namespace std; 528 529 const int N = 2e5 + 9, mod = 998244353; 530 using ll = long long; 531 532 int add(int a, int b){ 533 a += b; 534 if(a > mod) a -= mod; 535 if(a < 0) a += mod; 536 return a; 537 } 538 539 // dp[i][j] = number of arrays where starting element is i and gcd of the array is j 540 int dp[N], cur[N], uni[N]; 541 int sum[N]; 542 vector<int> d[N]; 543 void solve() { 544 int m; cin >> m; 545 for (int i = 1; i <= m; i++) { 546 dp[i] = cur[i] = 0; 547 uni[i] = 0; 548 sum[i] = 0; 549 } 550 int ans = 0; 551 ans = 0; 552 for (int i = m; i >= 1; i--) { 553 for (int j: d[i]) { 554 cur[j] = 0; 555 } 556 int sz = d[i].size(); 557 for(int idj = sz-1; idj >= 0; idj--){ 558 int j = d[i][idj]; 559 uni[j] = add(sum[j],sum[j]); 560 for(int idk = idj+1; idk < sz; idk++){ 561 int k = d[i][idk]; 562 if(k%j) continue; 563 uni[j] = add(uni[j],-uni[k]); 564 } 565 cur[j] = add(uni[j], - add(dp[j],dp[j])); 566 } 567 568 cur[i] += 1; 569 570 for (int j : d[i]) { 571 dp[j] = add(dp[j],cur[j]); 572 for(auto k : d[j]){ 573 sum[k] = add(sum[k],cur[j]); 574 } 575 ans = add(ans,cur[j]); 576 } 577 578 } 579 cout << ans << '\n'; 580 } 581 582 int32_t main() { 583 ios_base::sync_with_stdio(0); 584 cin.tie(0); 585 for (int i = 1; i < N; i++) { 586 for (int j = i; j < N; j += i) { 587 d[j].push_back(i); 588 } 589 } 590 int t = 1; 591 cin >> t; 592 while (t--) { 593 solve(); 594 } 595 return 0; 596 } 597 ``` 598 599 **Rate the Problem** 600 601 * Amazing problem: 602 * Good problem: 603 * Average problem: 604 * Bad problem: 605 * Didn't solve: 606 607 [2039F2 - Shohag Loves Counting (Hard Version)](/contest/2039/problem/F2) 608 609 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 610 611 **Tutorial** 612 613 Tutorial is loading... 614 615 **Code (unoptimized)** 616 617 ``` 618 #include<bits/stdc++.h> 619 using namespace std; 620 621 const int N = 1e6 + 9, mod = 998244353; 622 623 inline void add(int &x, int y) { 624 x = x + y >= mod ? x + y - mod : x + y; 625 } 626 int mob[N]; 627 void mobius() { 628 mob[1] = 1; 629 for (int i = 2; i < N; i++){ 630 mob[i]--; 631 for (int j = i + i; j < N; j += i) { 632 mob[j] -= mob[i]; 633 } 634 } 635 for (int i = 1; i < N; i++) { 636 mob[i] = (mob[i] % mod + mod) % mod; 637 } 638 } 639 vector<int> divs[N]; 640 int dp[N]; 641 int f[N]; 642 int tmp[N], ans[N]; 643 void solve() { 644 for (int i = 1; i < N; i++) { 645 for (int d: divs[i]) { 646 tmp[d] = (mod - f[d]) % mod; 647 for (int c: divs[d]) { 648 add(tmp[d], dp[c]); 649 } 650 tmp[d] = (2 * tmp[d] + 1) % mod; 651 } 652 653 // apply mobius inversion formula 654 for (int d: divs[i]) { 655 for (int c: divs[d]) { 656 add(dp[d], 1LL * mob[c] * tmp[d / c] % mod); 657 } 658 add(f[d], tmp[d]); 659 } 660 661 ans[i] = ans[i - 1]; 662 add(ans[i], f[i]); 663 } 664 } 665 666 int32_t main() { 667 ios_base::sync_with_stdio(0); 668 cin.tie(0); 669 for (int i = 1; i < N; i++) { 670 for (int j = i; j < N; j += i) { 671 divs[j].push_back(i); 672 } 673 } 674 mobius(); 675 solve(); 676 int t = 1; 677 cin >> t; 678 while (t--) { 679 int m; cin >> m; 680 cout << ans[m] << '\n'; 681 } 682 return 0; 683 } 684 ``` 685 686 **Code (optimized)** 687 688 ``` 689 #include<bits/stdc++.h> 690 using namespace std; 691 692 const int N = 1e6 + 9, mod = 998244353; 693 694 inline void add(int &x, int y) { 695 x = x + y >= mod ? x + y - mod : x + y; 696 } 697 int spf[N]; 698 void sieve() { 699 vector<int> p; 700 for(int i = 2; i < N; i++) { 701 if (spf[i] == 0) spf[i] = i, p.push_back(i); 702 int sz = p.size(); 703 for (int j = 0; j < sz && i * p[j] < N && p[j] <= spf[i]; j++) { 704 spf[i * p[j]] = p[j]; 705 } 706 } 707 } 708 int mob[N]; 709 void mobius() { 710 mob[1] = 1; 711 for (int i = 2; i < N; i++){ 712 mob[i]--; 713 for (int j = i + i; j < N; j += i) { 714 mob[j] -= mob[i]; 715 } 716 } 717 for (int i = 1; i < N; i++) { 718 mob[i] = (mob[i] % mod + mod) % mod; 719 } 720 } 721 int c[N]; 722 vector<int> divs[N]; 723 void gen_divs(int n) { // not sorted 724 int id = 1, x = n; 725 divs[n][0] = 1; 726 while (n > 1) { 727 int k = spf[n]; 728 int cur = 1, sz = id; 729 while (n % k == 0) { 730 cur *= k; 731 n /= k; 732 for (int i = 0; i < sz; i++) { 733 divs[x][id++] = divs[x][i] * cur; 734 } 735 } 736 } 737 } 738 739 void prec() { 740 sieve(); 741 // generate divisors without using push_back as its really slow on Codeforces 742 for (int i = 1; i < N; i++) { 743 for (int j = i; j < N; j += i) { 744 c[j]++; 745 } 746 divs[i].resize(c[i]); 747 gen_divs(i); 748 } 749 mobius(); 750 } 751 int dp[N]; 752 int f[N]; 753 int tmp[N], ans[N]; 754 void solve() { 755 for (int i = 1; i < N; i++) { 756 for (int d: divs[i]) { 757 tmp[d] = (mod - f[d]) % mod; 758 for (int c: divs[d]) { 759 add(tmp[d], dp[c]); 760 } 761 tmp[d] = (2 * tmp[d] + 1) % mod; 762 } 763 764 // apply mobius inversion formula 765 for (int d: divs[i]) { 766 for (int c: divs[d]) { 767 add(dp[d], 1LL * mob[c] * tmp[d / c] % mod); 768 } 769 add(f[d], tmp[d]); 770 } 771 772 ans[i] = ans[i - 1]; 773 add(ans[i], f[i]); 774 } 775 } 776 777 int32_t main() { 778 ios_base::sync_with_stdio(0); 779 cin.tie(0); 780 prec(); 781 solve(); 782 int t = 1; 783 cin >> t; 784 while (t--) { 785 int m; cin >> m; 786 cout << ans[m] << '\n'; 787 } 788 return 0; 789 } 790 ``` 791 792 **Rate the Problem** 793 794 * Amazing problem: 795 * Good problem: 796 * Average problem: 797 * Bad problem: 798 * Didn't solve: 799 800 [2039G - Shohag Loves Pebae](/contest/2039/problem/G) 801 802 Author: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho") 803 804 **Tutorial** 805 806 Tutorial is loading... 807 808 **Code** 809 810 ``` 811 #include<bits/stdc++.h> 812 using namespace std; 813 #include<ext/pb_ds/assoc_container.hpp> 814 #include<ext/pb_ds/tree_policy.hpp> 815 using namespace __gnu_pbds; 816 817 struct custom_hash { 818 static uint64_t splitmix64(uint64_t x) { 819 x += 0x9e3779b97f4a7c15; 820 x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; 821 x = (x ^ (x >> 27)) * 0x94d049bb133111eb; 822 return x ^ (x >> 31); 823 } 824 size_t operator()(uint64_t x) const { 825 static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); 826 return splitmix64(x + FIXED_RANDOM); 827 } 828 }; 829 830 const int N = 1e6 + 9, T = 1e7 + 9, RT = 33333, mod = 998244353; 831 using ll = long long; 832 833 int power(int n, long long k) { 834 int ans = 1 % mod; 835 while (k) { 836 if (k & 1) ans = (long long) ans * n % mod; 837 n = (long long) n * n % mod; 838 k >>= 1; 839 } 840 return ans; 841 } 842 843 int SQRT(int n) { 844 int x = sqrt(n); 845 while (x * x < n) ++x; 846 while (x * x > n) --x; 847 return x; 848 } 849 850 int spf[T], id[T], DIAMETER, mu[T]; 851 vector<int> primes; // 1 indexed 852 int prefix_prime_count[T], prefix_sum_mu[T]; 853 void init() { 854 mu[1] = 1; 855 for(int i = 2; i < T; i++) { 856 if (spf[i] == 0) spf[i] = i, mu[i] = i <= DIAMETER ? 0 : -1, primes.push_back(i); 857 int sz = primes.size(); 858 for (int j = 0; j < sz && i * primes[j] < T && primes[j] <= spf[i]; j++) { 859 spf[i * primes[j]] = primes[j]; 860 if (i % primes[j] == 0) mu[i * primes[j]] = 0; 861 else mu[i * primes[j]] = mu[i] * (primes[j] <= DIAMETER ? 0 : -1); 862 } 863 } 864 primes.insert(primes.begin(), 0); 865 for (int i = 1; i < primes.size(); i++) { 866 id[primes[i]] = i; 867 } 868 for (int i = 2; i < T; i++) { 869 prefix_prime_count[i] = prefix_prime_count[i - 1] + (spf[i] == i); 870 } 871 for (int i = 1; i < T; i++) prefix_sum_mu[i] = prefix_sum_mu[i - 1] + mu[i]; 872 } 873 int cnt[N]; // count of nodes having each diameter 874 int m; 875 namespace GoodNumbers { // numbers which aren't divisible by the first k primes 876 gp_hash_table<int, int, custom_hash> mp[RT << 1]; 877 int count_num(int n, int k) { // n is a floor value, returns good numbers <= n 878 if (k == 0 or n == 0) return n; 879 if (primes[k] >= n) return 1; 880 if (n < T and 1LL * primes[k] * primes[k] > n) { 881 return 1 + prefix_prime_count[n] - k; 882 } 883 if (mp[k].find(n) != mp[k].end()) return mp[k][n]; 884 int ans; 885 if (1LL * primes[k] * primes[k] > n) { 886 int x = upper_bound(primes.begin(), primes.begin() + k, (int)SQRT(n)) - primes.begin() - 1; 887 ans = count_num(n, x) - (k - x); 888 } 889 else ans = count_num(n, k - 1) - count_num(n / primes[k], k - 1); 890 mp[k][n] = ans; 891 return ans; 892 } 893 }; 894 895 vector<pair<int, int>> v; 896 namespace Dirichlet { 897 // good number = numbers that aren't divisible by any prime <= DIAMETER 898 // we will run dirichlet imagining there exists no prime <= DIAMETER 899 gp_hash_table<int, int, custom_hash> mp; 900 int p_c(int n) { 901 return n < 1 ? 0 : 1; 902 } 903 int p_g(int n) { 904 return GoodNumbers::count_num(n, v.back().first); 905 } 906 int solve (int x) { // sum of mob[i] over 1 <= i <= x and i is a good number 907 if (x < T) return prefix_sum_mu[x]; 908 if (mp.find(x) != mp.end()) return mp[x]; 909 int ans = 0; 910 for (int i = 2, last; i <= x; i = last + 1) { 911 last = x / (x / i); 912 ans += solve(x / i) * (p_g(last) - p_g(i - 1)); 913 } 914 ans = p_c(x) - ans; 915 return mp[x] = ans; 916 } 917 }; 918 919 int count_primes(int n) { 920 if (n < T) return prefix_prime_count[n]; 921 int x = SQRT(n); 922 int k = upper_bound(primes.begin(), primes.end(), x) - primes.begin() - 1; 923 return GoodNumbers::count_num(n, k) + k - 1; 924 } 925 926 // diameter > 2 * sqrt(m) 927 void solve_large() { 928 // only primes are good, so count total ways 929 // and subtract where gcd is prime (means all nodes have a fixed prime) 930 int total_ways = 1; 931 int primes_under_m = count_primes(m); 932 for (auto [k, c]: v) { 933 if (m <= primes[k]) break; 934 total_ways = 1LL * total_ways * power((primes_under_m - k + 1) % mod, c) % mod; // 1 or a prime > k 935 } 936 int bad_ways = (max(0, primes_under_m - v.back().first)) % mod; 937 int ans = (total_ways - bad_ways + mod) % mod; 938 cout << ans << '\n'; 939 } 940 941 // diameter <= 2 * sqrt(m) 942 void solve_small() { 943 int ans = 0; 944 for (int l = 1, r; l <= m; l = r + 1) { 945 int x = m / l; 946 r = m / x; 947 int cur = ((Dirichlet::solve(r) - Dirichlet::solve(l - 1)) % mod + mod) % mod; 948 if (cur) { 949 int mul = 1; 950 for (auto [k, c]: v) { 951 if (x <= primes[k]) break; 952 mul = 1LL * mul * power(GoodNumbers::count_num(x, k) % mod, c) % mod; 953 } 954 ans += 1LL * cur * mul % mod; 955 ans %= mod; 956 } 957 } 958 cout << ans << '\n'; 959 } 960 961 vector<int> g[N]; 962 int dp[N], up[N]; 963 void dfs(int u, int p = 0) { 964 dp[u] = 0; 965 if (p) g[u].erase(find(g[u].begin(), g[u].end(), p)); 966 for (auto v: g[u]) { 967 if (v ^ p) { 968 dfs(v, u); 969 dp[u] = max(dp[u], dp[v] + 1); 970 } 971 } 972 } 973 int pref[N], suf[N]; 974 void dfs2(int u) { 975 int sz = g[u].size(); 976 for (int i = 0; i < sz; i++) { 977 int v = g[u][i]; 978 pref[i] = dp[v] + 1; 979 if (i) pref[i] = max(pref[i], pref[i - 1]); 980 } 981 for (int i = sz - 1; i >= 0; i--) { 982 int v = g[u][i]; 983 suf[i] = dp[v] + 1; 984 if (i + 1 < sz) suf[i] = max(suf[i], suf[i + 1]); 985 } 986 for (int i = 0; i < sz; i++) { 987 int v = g[u][i]; 988 int cur = up[u]; 989 if (i) cur = max(cur, pref[i - 1]); 990 if (i + 1 < sz) cur = max(cur, suf[i + 1]); 991 up[v] = cur + 1; 992 } 993 for (auto v: g[u]) { 994 dfs2(v); 995 } 996 } 997 int mx_d[N]; 998 int32_t main() { 999 ios_base::sync_with_stdio(0); 1000 cin.tie(0); 1001 int n; cin >> n >> m; 1002 for (int i = 1; i < n; i++) { 1003 int u, v; cin >> u >> v; 1004 g[u].push_back(v); 1005 g[v].push_back(u); 1006 } 1007 dfs(1); 1008 dfs2(1); 1009 for (int u = 1; u <= n; u++) { 1010 vector<int> vec; 1011 if (u != 1) vec.push_back(up[u]); 1012 for (auto v: g[u]) { 1013 vec.push_back(dp[v] + 1); 1014 } 1015 sort(vec.rbegin(), vec.rend()); 1016 mx_d[u] = vec[0]; 1017 if (vec.size() > 1) { 1018 mx_d[u] += vec[1]; 1019 } 1020 mx_d[u] += 1; 1021 } 1022 for (int i = 1; i <= n; i++) { 1023 cnt[mx_d[i]]++; 1024 DIAMETER = max(DIAMETER, mx_d[i]); 1025 } 1026 1027 init(); 1028 1029 int last_prime = 0; 1030 for (int i = 2; i <= DIAMETER; i++) { 1031 if (spf[i] == i) last_prime = i; 1032 if (cnt[i]) { 1033 int k = id[last_prime]; 1034 if (!v.empty() and v.back().first == k) { 1035 v.back().second += cnt[i]; 1036 } else { 1037 v.push_back({k, cnt[i]}); 1038 } 1039 } 1040 } 1041 1042 if (DIAMETER > 2 * SQRT(m)) solve_large(); 1043 else solve_small(); 1044 return 0; 1045 } 1046 ``` 1047 1048 **Rate the Problem** 1049 1050 * Amazing problem: 1051 * Good problem: 1052 * Average problem: 1053 * Bad problem: 1054 * Didn't solve: 1055 1056 [2039H1 - Cool Swap Walk (Easy Version)](/contest/2039/problem/H1) 1057 1058 Author: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm") 1059 1060 **Tutorial** 1061 1062 We can observe that this kind of path is imporatnt — when we are in $(x, x)$, we only perform one of the following two kind of moves: 1063 1064 **Move 1** 1065 1066 $ (x, x) \rightarrow (x, x+1) \rightarrow (x+1, x+1) $ 1067 1068 This move transforms $[\ldots,a_x, a_{x+1},\ldots]$ into $[\ldots,a_{x+1}, a_{x},\ldots]$. 1069 1070 **Move 2** 1071 1072 $ (x, x) \rightarrow (x, x+1) \rightarrow (x, x+2) \rightarrow (x+1, x+2) \rightarrow (x+2, x+2) $ 1073 1074 This move transforms $[\ldots,a_x, a_{x+1},a_{x+2},\ldots]$ into $[\ldots,a_{x+2}, a_{x+1},a_{x},\ldots]$. 1075 1076 **Summary of the path:** 1077 1078 Note the arrays before and after the path as $a$ and $a'$, respectively. We can see $a'_n=a_1$, and $[a'_1,\ldots,a'_{n-1}]$ can be obtained from $[a_2,\ldots,a_{n}]$ through the following transformation: 1079 1080 * Swap any two adjacent numbers of $[a_2,\ldots,a_{n}]$, but each number can be swapped at most once. 1081 1082 This inspires us to use [Odd-Even Sort](https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort) algorithm. 1083 1084 **Steps to Achieve the Sorted Array:** 1085 1086 Step $1$: **Initialize $a_1 = mn$:** If $a_1 \neq mn$, where $mn$ is the minimum of the array, use the following path: 1087 1088 $ (1, 1) \rightarrow (1, p_1) \rightarrow (p_1, p_1) \rightarrow (p_1, n) \rightarrow (n, n) $ 1089 1090 This sequence ensures that $a_1 = mn$. 1091 1092 Then, repeat steps $2$ and $3$ until the array is sorted. 1093 1094 Step $2$: **Perform Odd-Even Sorting:** Perform an [Odd-Even Sort](https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort) (a round of comparison) using the key path above on the subarray $a_2, \dots, a_n$. 1095 1096 Step $3$: **Maintain the orderliness of $[a_{2}, \dots ,a_{n}]$ while repeatedly making $a_1 = mn$:** After step $2$, we want $mn$ back to the head of the array. To achieve this, perform the following operations: 1097 1098 $ (1, 1) \rightarrow (1, n) \rightarrow (n, n) $ 1099 1100 This sequence transforms the array as follows: 1101 1102 $ [a_1, a_2, \dots, a_n(a_n=mn)] \rightarrow [a'_1, a'_2, \dots, a'_n]=[a_n, a_{n-1}, a_1, a_2, \dots, a_{n-2}] $ 1103 1104 When this is performed after an odd-even sort, it ensures that: 1105 1106 * $mn$ is back to the head of the array. 1107 * The subarray $a_1, \dots, a_{n-1}$ has been cyclically shifted. 1108 1109 **Handling Continuous Cyclic Shifts in Odd-Even Sort:** 1110 1111 * **Even Length ($n-1$ is even):** Cyclic shifting does not affect the odd-even sort. You can continue applying the sort as usual. 1112 * **Odd Length ($n-1$ is odd):** A small modification is needed. Specifically, First compare $(a_3,a_4),(a_5,a_6),\ldots$ instead of $(a_2,a_3),(a_4,a_5),\ldots$ This adjustment ensures that the odd-even sort operates correctly despite the continuous cyclic shifts. 1113 1114 Overall, we obtained a sorted array using $2n$ walks. 1115 1116 **Code** 1117 1118 ``` 1119 #include <map> 1120 #include <set> 1121 #include <cmath> 1122 #include <ctime> 1123 #include <queue> 1124 #include <stack> 1125 #include <cstdio> 1126 #include <cstdlib> 1127 #include <vector> 1128 #include <cstring> 1129 #include <algorithm> 1130 #include <iostream> 1131 #include <bitset> 1132 using namespace std; 1133 typedef double db; 1134 typedef long long ll; 1135 typedef unsigned long long ull; 1136 const int N=2010; 1137 int T,n,mn,tot; 1138 int a[N]; 1139 vector<int> X[N],Y[N]; 1140 1141 void path1(int num) //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->... 1142 { 1143 for(int i=1;i<=n;i++) 1144 { 1145 X[num].push_back(i),Y[num].push_back(i); 1146 if(i!=n) 1147 { 1148 X[num].push_back(i),Y[num].push_back(i+1); 1149 swap(a[i],a[i+1]); 1150 } 1151 } 1152 } 1153 1154 void path2(int num) //(1,1)->(1,n)->(n,n) 1155 { 1156 for(int i=1;i<=n;i++) 1157 { 1158 X[num].push_back(1),Y[num].push_back(i); 1159 swap(a[1],a[i]); 1160 } 1161 for(int i=2;i<=n;i++) 1162 { 1163 X[num].push_back(i),Y[num].push_back(n); 1164 swap(a[i],a[n]); 1165 } 1166 } 1167 1168 void walk1(int j) 1169 { 1170 X[tot].push_back(j-1),Y[tot].push_back(j); 1171 X[tot].push_back(j-1),Y[tot].push_back(j+1); 1172 X[tot].push_back(j),Y[tot].push_back(j+1); 1173 X[tot].push_back(j+1),Y[tot].push_back(j+1); 1174 swap(a[j-1],a[j+1]); 1175 } 1176 1177 void walk2(int j) 1178 { 1179 X[tot].push_back(j-1),Y[tot].push_back(j); 1180 X[tot].push_back(j),Y[tot].push_back(j); 1181 X[tot].push_back(j),Y[tot].push_back(j+1); 1182 X[tot].push_back(j+1),Y[tot].push_back(j+1); 1183 swap(a[j-1],a[j]); 1184 swap(a[j],a[j+1]); 1185 } 1186 1187 int main() 1188 { 1189 scanf("%d",&T); 1190 while(T--) 1191 { 1192 scanf("%d",&n); 1193 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 1194 mn=n;tot=0; 1195 for(int i=1;i<=n;i++) mn=min(mn,a[i]); 1196 for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear(); 1197 int p1; 1198 for(int i=1;i<=n;i++) if(a[i]==mn) p1=i; 1199 if(p1!=1) 1200 { 1201 tot++; 1202 for(int i=1;i<=p1;i++) X[tot].push_back(1),Y[tot].push_back(i),swap(a[1],a[i]); 1203 for(int i=2;i<=p1;i++) X[tot].push_back(i),Y[tot].push_back(p1),swap(a[i],a[p1]); 1204 for(int i=p1+1;i<=n;i++) X[tot].push_back(p1),Y[tot].push_back(i),swap(a[p1],a[i]); 1205 for(int i=p1+1;i<=n;i++) X[tot].push_back(i),Y[tot].push_back(n),swap(a[i],a[n]); 1206 } 1207 for(int i=2;i<=n;i++) 1208 { 1209 tot++; 1210 X[tot].push_back(1),Y[tot].push_back(1); 1211 if(n&1) 1212 { 1213 if(i&1) 1214 { 1215 for(int j=2;j<=n;j+=2) 1216 { 1217 if(j+1==i) walk2(j); 1218 else if(a[j]>a[j+1]) walk1(j); 1219 else walk2(j); 1220 } 1221 } 1222 else 1223 { 1224 for(int j=2;j<=n;j+=2) 1225 { 1226 if(a[j]>a[j+1]) walk1(j); 1227 else walk2(j); 1228 } 1229 } 1230 } 1231 else 1232 { 1233 if(i&1) 1234 { 1235 for(int j=2;j<=n;j+=2) 1236 { 1237 if(j==i-1) 1238 { 1239 X[tot].push_back(j-1),Y[tot].push_back(j); 1240 X[tot].push_back(j),Y[tot].push_back(j); 1241 swap(a[j-1],a[j]); 1242 j--; 1243 } 1244 else if(a[j]>a[j+1]) walk1(j); 1245 else walk2(j); 1246 } 1247 } 1248 else 1249 { 1250 for(int j=2;j<=n;j+=2) 1251 { 1252 if(j==i) 1253 { 1254 X[tot].push_back(j-1),Y[tot].push_back(j); 1255 X[tot].push_back(j),Y[tot].push_back(j); 1256 swap(a[j-1],a[j]); 1257 j--; 1258 } 1259 else if(a[j]>a[j+1]) walk1(j); 1260 else walk2(j); 1261 } 1262 } 1263 } 1264 path2(++tot); 1265 } 1266 printf("%d\n",tot); 1267 for(int i=1;i<=tot;i++) 1268 { 1269 for(int j=1;j<2*n-1;j++) 1270 { 1271 if(X[i][j]==X[i][j-1]) printf("R"); 1272 else printf("D"); 1273 } 1274 printf("\n"); 1275 } 1276 1277 } 1278 1279 return 0; 1280 } 1281 ``` 1282 1283 **Rate the Problem** 1284 1285 * Amazing problem: 1286 * Good problem: 1287 * Average problem: 1288 * Bad problem: 1289 * Didn't solve: 1290 1291 [2039H2 - Cool Swap Walk (Hard Version)](/contest/2039/problem/H2) 1292 1293 Author: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm") 1294 1295 **Tutorial** 1296 1297 First, read the editorial of the easy version. We can see that the bottleneck lies in the fact that after every round of odd-even sorting, we need to perform a walk operation to ensure that $a_1 = mn$. 1298 1299 The following method can break through this bottleneck: for simplicity, let's assume $n$ is even. Define the numbers smaller than or equal to $\frac{n}{2}$ as $S$, and the numbers bigger than $\frac{n}{2}$ as $B$. If we have $a = [S, \ldots, S, B, \ldots, B]$, we can repeatedly perform key path operations to get the following sequence: 1300 1301 1. $[S, \ldots, S, B, \ldots, B] \to [S, \ldots, S, B, \ldots, B, S] \to [S, \ldots, S, B, \ldots, B, S, S] \to \ldots \to [B, \ldots, B, S, \ldots, S]$ In this process, we only perform odd-even sorting for the subarray $[B, \ldots, B]$. 1302 2. $[B, \ldots, B, S, \ldots, S] \to [B, \ldots, B, S, \ldots, S, B] \to [B, \ldots, B, S, \ldots, B, B] \to \ldots \to [S, \ldots, S, B, \ldots, B]$ In this process, we only perform odd-even sorting for the subarray $[S, \ldots, S]$. 1303 1304 After that, the array is sorted. 1305 1306 Finally, the only remaining problem is how to arrange $a = [S, \ldots, S, B, \ldots, B]$. 1307 1308 Assume we have $k$ positions $p_1, p_2, \ldots, p_k$ such that $1 \lt p_1 \lt p_2 \lt \ldots \lt p_k \leq n$. Consider what the following operations are doing: 1309 1310 $(1, 1) \to (1, p_1)\to (2, p_1) \to (2, p_2)\to (3, p_2) \to \ldots \to (k, p_k)$ 1311 1312 If we ignore the other numbers,these operations correspond to: 1313 1314 $\text{swap}(a_1, a_{p_1}), \text{swap}(a_2, a_{p_2}), \ldots$ 1315 1316 Then, we can take any path from $(k, p_k)$ to $(n, n)$. 1317 1318 At first, we perform one operation to set $a_1 = n$, then choose $\frac{n}{2}$ positions $p_1, p_2, \ldots, p_{\frac{n}{2}}$ to obtain $a = [S, \ldots, S, B, \ldots, B]$. 1319 1320 For $n$ being odd, we need two additional operations for some little adjustments. 1321 1322 Overall, we obtained a sorted array using $n + 4$ walks. 1323 1324 **Code** 1325 1326 ``` 1327 #include <map> 1328 #include <set> 1329 #include <cmath> 1330 #include <ctime> 1331 #include <queue> 1332 #include <stack> 1333 #include <cstdio> 1334 #include <cstdlib> 1335 #include <vector> 1336 #include <cstring> 1337 #include <algorithm> 1338 #include <iostream> 1339 #include <bitset> 1340 using namespace std; 1341 typedef double db; 1342 typedef long long ll; 1343 typedef unsigned long long ull; 1344 const int N=2010; 1345 int T,n,tot; 1346 int a[N]; 1347 vector<int> X[N],Y[N]; 1348 1349 void path1(int num) //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->... 1350 { 1351 for(int i=1;i<=n;i++) 1352 { 1353 X[num].push_back(i),Y[num].push_back(i); 1354 if(i!=n) 1355 { 1356 X[num].push_back(i),Y[num].push_back(i+1); 1357 swap(a[i],a[i+1]); 1358 } 1359 } 1360 } 1361 1362 void path2(int num) //(1,1)->(1,n)->(n,n) 1363 { 1364 for(int i=1;i<=n;i++) 1365 { 1366 X[num].push_back(1),Y[num].push_back(i); 1367 swap(a[1],a[i]); 1368 } 1369 for(int i=2;i<=n;i++) 1370 { 1371 X[num].push_back(i),Y[num].push_back(n); 1372 swap(a[i],a[n]); 1373 } 1374 } 1375 1376 void path3(int num,vector<int> p) //swap(1,p[0]),(2,p[1]),... note p[0]!=1 1377 { 1378 for(int i=1;i<=p[0];i++) 1379 { 1380 X[num].push_back(1),Y[num].push_back(i); 1381 swap(a[1],a[i]); 1382 } 1383 for(int i=1;i<p.size();i++) 1384 { 1385 for(int j=p[i-1];j<=p[i];j++) 1386 { 1387 X[num].push_back(i+1),Y[num].push_back(j); 1388 swap(a[i+1],a[j]); 1389 } 1390 } 1391 int x=p.size(),y=p.back(); 1392 while(x!=n) 1393 { 1394 x++; 1395 X[num].push_back(x),Y[num].push_back(y); 1396 swap(a[x],a[y]); 1397 } 1398 while(y!=n) 1399 { 1400 y++; 1401 X[num].push_back(x),Y[num].push_back(y); 1402 swap(a[x],a[y]); 1403 } 1404 } 1405 1406 void walk1(int j) 1407 { 1408 X[tot].push_back(j-1),Y[tot].push_back(j); 1409 X[tot].push_back(j-1),Y[tot].push_back(j+1); 1410 X[tot].push_back(j),Y[tot].push_back(j+1); 1411 X[tot].push_back(j+1),Y[tot].push_back(j+1); 1412 swap(a[j-1],a[j+1]); 1413 } 1414 1415 void walk2(int j) 1416 { 1417 X[tot].push_back(j-1),Y[tot].push_back(j); 1418 X[tot].push_back(j),Y[tot].push_back(j); 1419 X[tot].push_back(j),Y[tot].push_back(j+1); 1420 X[tot].push_back(j+1),Y[tot].push_back(j+1); 1421 swap(a[j-1],a[j]); 1422 swap(a[j],a[j+1]); 1423 } 1424 1425 void walk3(int j) 1426 { 1427 X[tot].push_back(j-1),Y[tot].push_back(j); 1428 X[tot].push_back(j),Y[tot].push_back(j); 1429 swap(a[j-1],a[j]); 1430 } 1431 1432 void init() 1433 { 1434 scanf("%d",&n); 1435 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 1436 tot=0; 1437 for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear(); 1438 vector<pair<int,int> > pr; 1439 for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i)); 1440 sort(pr.begin(),pr.end()); 1441 for(int i=1;i<=n;i++) a[pr[i-1].second]=i; 1442 } 1443 1444 void step1() 1445 { 1446 int p1,pn; 1447 vector<int> p; 1448 for(int i=1;i<=n;i++) if(a[i]==1) p1=i; 1449 if(p1!=1) 1450 { 1451 p.push_back(p1); 1452 path3(++tot,p); 1453 } 1454 if(n==2) return ; 1455 tot++; 1456 X[tot].push_back(1),Y[tot].push_back(1); 1457 for(int j=2;j<=n;j+=2) 1458 { 1459 if(j+1>n) walk3(j); 1460 else if(a[j]==n) walk1(j); 1461 else walk2(j); 1462 } 1463 p1=n; 1464 for(int i=1;i<=n;i++) if(a[i]==n) pn=i; 1465 p.clear(); 1466 p.push_back(pn);p.push_back(p1); 1467 path3(++tot,p); 1468 p.clear(); 1469 for(int i=1;i<=n;i++) if(a[i]<=(n+1)/2) p.push_back(i); 1470 path3(++tot,p); 1471 } 1472 1473 void step2() 1474 { 1475 int head; 1476 if(n&1) 1477 { 1478 for(int t=1;t<=2;t++) 1479 { 1480 head=n/2+2; 1481 for(int i=1;i<=n/2+(t==1);i++) 1482 { 1483 tot++; 1484 X[tot].push_back(1),Y[tot].push_back(1); 1485 for(int j=2;j<=n;j++) 1486 { 1487 if(!(head<=j&&j<=head+n/2-1)) walk3(j); 1488 else if(j==head&&(head&1)) walk3(j); 1489 else 1490 { 1491 if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j); 1492 else if(a[j]>a[j+1]) walk1(j),j++; 1493 else walk2(j),j++; 1494 } 1495 } 1496 head--; 1497 } 1498 } 1499 } 1500 else 1501 { 1502 for(int t=1;t<=2;t++) 1503 { 1504 head=n/2+1; 1505 for(int i=1;i<=n/2;i++) 1506 { 1507 tot++; 1508 X[tot].push_back(1),Y[tot].push_back(1); 1509 for(int j=2;j<=n;j++) 1510 { 1511 if(!(head<=j&&j<=head+n/2-1)) walk3(j); 1512 else if(j==head&&(head&1)) walk3(j); 1513 else 1514 { 1515 if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j); 1516 else if(a[j]>a[j+1]) walk1(j),j++; 1517 else walk2(j),j++; 1518 } 1519 } 1520 head--; 1521 } 1522 } 1523 } 1524 } 1525 1526 void output() 1527 { 1528 printf("%d\n",tot); 1529 for(int i=1;i<=tot;i++) 1530 { 1531 for(int j=1;j<2*n-1;j++) 1532 { 1533 if(X[i][j]==X[i][j-1]) printf("R"); 1534 else printf("D"); 1535 } 1536 printf("\n"); 1537 } 1538 } 1539 1540 int main() 1541 { 1542 scanf("%d",&T); 1543 while(T--) 1544 { 1545 init(); 1546 step1(); 1547 step2(); 1548 output(); 1549 } 1550 1551 return 0; 1552 } 1553 ``` 1554 1555 **Rate the Problem** 1556 1557 * Amazing problem: 1558 * Good problem: 1559 * Average problem: 1560 * Bad problem: 1561 * Didn't solve: