codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2039.md (36945B)


      1 Source: https://codeforces.com/blog/entry/136523
      2 
      3 Thanks for participating in the contest [![blobheart](/predownloaded/d7/cc/d7cc8b5ea81178880175de5a048032c05631f9b7.png)](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: