codeforces-scrape

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

2060.md (27608B)


      1 Source: https://codeforces.com/blog/entry/138342
      2 
      3 **Rating Predictions**
      4 
      5 | Predictor | A | B | C | D | E | F | G |
      6 | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1000 | 1100 | 1300 | 1600 | 1900 | 2400 |
      8 | [cry](/profile/cry "International Master cry") | 800 | 1000 | 1000 | 1200 | 1700 | 2000 | 2400 |
      9 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 1000 | 1000 | 1400 | 1700 | 2000 | 2400 |
     10 | [DivinePunishment](/profile/DivinePunishment "Expert DivinePunishment") | 800 | 1200 | 1100 | 1200 | 1700 | 2000 | 2300 |
     11 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 1000 | 1000 | 1400 | 1800 | 2000 | 2400 |
     12 | [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") | 800 | 1100 | 1200 | 1600 | 1800 | 2100 | 2400 |
     13 | [macaquedev](/profile/macaquedev "Expert macaquedev") | 800 | 1000 | 1500 | 1400 | 1300 | 2000 | 1900 |
     14 | [Intellegent](/profile/Intellegent "Master Intellegent") | 800 | 900 | 1200 | 1400 | 1700 | 2100 | 2400 |
     15 | [yoru_sacri](/profile/yoru_sacri "Candidate Master yoru_sacri") | 800 | 900 | 1300 | 1100 | 1700 | 2000 |  |
     16 | [efishel](/profile/efishel "Master efishel") | 800 | 800 | 800 | 1300 | 1600 | 1900 | 2100 |
     17 | [Friedrich](/profile/Friedrich "Master Friedrich") | 800 | 800 | 1100 | 1300 | 1500 | 2100 | 2300 |
     18 | [larush](/profile/larush "Expert larush") | 800 | 1000 | 1100 | 1200 | 1600 | 2000 | 2400 |
     19 | [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") | 800 | 800 | 900 | 1200 | 1500 | 1900 | 2100 |
     20 
     21 |  | A | B | C | D | E | F | G |
     22 | --- | --- | --- | --- | --- | --- | --- | --- |
     23 | **Average** | 800 | 961.5 | 1100 | 1307.7 | 1630.8 | 2000 | 2291.7 |
     24 | **Actual** | 800 | 1000 | 900 | 1100 | 1500 | 2200 | 2400 |
     25 
     26 #### [2060A - Fibonacciness](/contest/2060/problem/A "Codeforces Round 998 (Div. 3)")
     27 
     28 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")   
     29  Analysis: [larush](/profile/larush "Expert larush")
     30 
     31 **Solution 1**
     32 
     33 We can notice that the possible values of $a_3$ ranges from $-99$ to $200$. Thus, we can iterate over all values of $a_3$ from $-99$ to $200$, and for each value, compute the Fibonacciness of the sequence. The maximal of all these values gives the solution to the problem.
     34 
     35 Time Complexity : $O(3*a_{max})$
     36 
     37 **Solution 2**
     38 
     39 $a_3$ can be represented as either of the following:
     40 
     41 $a_3 = a_1 + a_2$, or
     42 
     43 $a_3 = a_4 - a_2$, or
     44 
     45 $a_3 = a_5 - a_4$.
     46 
     47 These are at most 3 possible values. Notice that any value of $a_3$ which increases the Fibonacciness must belong to one of the above values (Think why!). So, in order to increase the Fibonacciness of the sequence, we should choose the most frequent of the above values. Then, in the end, we can calculate the Fibonacciness of the sequence after choosing the best value for $a_3$.
     48 
     49 Time Complexity : $O(1)$
     50 
     51 **Code (C++)**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 using namespace std;
     56 using ll = long long;
     57 using vll = vector <ll>;
     58 using ii = pair <ll, ll>;
     59 using vii = vector <ii>;
     60 
     61 void tc () {
     62     vll ve(4);
     63     for (ll &i : ve) cin >> i;
     64     set <ll> st;
     65     st.insert(ve[3]-ve[2]);
     66     st.insert(ve[2]-ve[1]);
     67     st.insert(ve[0]+ve[1]);
     68     cout << 4-st.size() << '\n';
     69 }
     70 
     71 int main () {
     72     cin.tie(nullptr) -> sync_with_stdio(false);
     73     ll T; cin >> T; while (T--) { tc(); }
     74     return 0;
     75 }
     76 ```
     77 
     78 **Rate The Problem!**
     79 
     80 * Heat
     81 * Mid
     82 * Horrendous
     83 * Didn't Solve
     84 
     85 #### [2060B - Farmer John's Card Game](/contest/2060/problem/B "Codeforces Round 998 (Div. 3)")
     86 
     87 Problem Credits: [Lilypad](/profile/Lilypad "Candidate Master Lilypad")   
     88  Analysis: [larush](/profile/larush "Expert larush")
     89 
     90 **Solution**
     91 
     92 Assume the cows are initially ordered correctly. A solution exists if the first cow can place $0$, the second cow can place $1$, and so on, continuing with the first cow placing $n$, the second cow placing $n+1$, and so forth. Observing the pattern, the first cow must be able to place ${0, n, 2n, \dots}$, the second ${1, n+1, 2n+1, \dots}$, and in general, the $i$-th cow (where $i \in [0, n-1]$) must be able to place ${i, n+i, 2n+i, \dots}$.
     93 
     94 For each cow, sorting their cards reveals whether they satisfy this condition: the difference between adjacent cards in the sorted sequence must be $n$. If any cow's cards do not meet this criterion, the solution does not exist, and we output $-1$.
     95 
     96 If the cows are not ordered correctly, we need to rearrange them. To construct the solution, find the index of the cow holding card $i$ for each $i \in [0, n-1]$. Since the cards of each cow are sorted, denote $\texttt{min_card}$ as the smallest card a cow holds. Using an array $p$, iterate over each cow $c$ from $0$ to $n-1$ and set $p_\texttt{min_card} = c$. Finally, iterate $i$ from $0$ to $n-1$ and output $p_i$.
     97 
     98 Time Complexity : $O(nmlog(m))$. Note that sorting is not necessary, and a solution with complexity up to $O((nm)^2)$ will still pass.
     99 
    100 **Code (C++)**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 using ll = long long;
    106 using vll = vector <ll>;
    107 using ii = pair <ll, ll>;
    108 using vii = vector <ii>;
    109 
    110 void tc () {
    111     ll n, m;
    112     cin >> n >> m;
    113     vector <vll> ve(n, vll(m));
    114     vll p(n, -16);
    115     bool val = true;
    116     ll c = 0;
    117     for (vll &we : ve) {
    118         for (ll &i : we) cin >> i;
    119         ll minN = *min_element(we.begin(), we.end());
    120         if (minN < n) p[minN] = c++;
    121         val &= minN < n;
    122         sort(we.begin(), we.end());
    123         ll last = we[0]-n;
    124         for (ll i : we) {
    125             val &= last+n == i;
    126             last = i;
    127         }
    128     }
    129     if (!val) {
    130         cout << "-1\n";
    131         return;
    132     }
    133     for (ll i : p) cout << i+1 << ' ';
    134     cout << '\n';
    135 }
    136 
    137 int main () {
    138     cin.tie(nullptr) -> sync_with_stdio(false);
    139     ll T; cin >> T; while (T--) { tc(); }
    140     return 0;
    141 }
    142 ```
    143 
    144 **Rate The Problem!**
    145 
    146 * Heat
    147 * Mid
    148 * Horrendous
    149 * Didn't Solve
    150 
    151 #### [2060C - Game of Mathletes](/contest/2060/problem/C "Codeforces Round 998 (Div. 3)")
    152 
    153 Problem Credits: [Friedrich](/profile/Friedrich "Master Friedrich")   
    154  Analysis: [macaquedev](/profile/macaquedev "Expert macaquedev")
    155 
    156 **Solution**
    157 
    158 Note that Bob has all the power in this game, because the order in which Alice picks numbers is irrelevant, since Bob can always pick the optimal number to give himself a point. Therefore, we can just ignore Alice and play the game from Bob's perspective.
    159 
    160 From this point on, a "paired" number is any number $a$ on the blackboard such that there exists a $b$ on the blackboard such that $a+b=k$.
    161 
    162 Bob's strategy is as follows:
    163 
    164 * if Alice picks a paired number, Bob should pick the other number in the pair.
    165 * if Alice picks an unpaired number, Bob can pick any other unpaired number, it doesn't matter which.
    166 
    167 This always works because the number of "unpaired numbers" is always even, since $n$ is even and the number of "paired numbers" will always be even. Therefore, for every unpaired number Alice picks, Bob will always have an unpaired number to respond with.
    168 
    169 Therefore, the final score is just the number of pairs in the input. To count them, use a map of counts $c$ such that $c_x$ is the number of occurrences of $x$ on the whiteboard. Then, for each number from $1$ to $\lfloor \frac{k}{2} \rfloor$, take the minimum of $c_x$ and $c_{k-x}$, and add that to the total. Remember the edge case where $k$ is even and $x = \frac{k}{2}$. The number of pairs here is just $\lfloor \frac{c_x}{2} \rfloor$.
    170 
    171 **Code (C++)**
    172 
    173 ```
    174 #include <bits/stdc++.h>
    175 using namespace std;
    176 using ll = long long;
    177 using vll = vector <ll>;
    178 using ii = pair <ll, ll>;
    179 using vii = vector <ii>;
    180 
    181 void tc () {
    182     ll n, k;
    183     cin >> n >> k;
    184     vll ve(n);
    185     for (ll &i : ve) cin >> i;
    186     vll th(k+1, 0);
    187     for (ll i : ve) {
    188         if (i >= k) continue;
    189         th[i]++;
    190     }
    191     ll ans = 0;
    192     for (ll i = 1; i < k; i++) {
    193         if (i == k-i) {
    194             ans += th[i]/2;
    195             continue;
    196         }
    197         ll minN = min(th[i], th[k-i]);
    198         th[i] -= minN;
    199         th[k-i] -= minN;
    200         ans += minN;
    201     }
    202     cout << ans << '\n';
    203 }
    204 
    205 int main () {
    206     cin.tie(nullptr) -> sync_with_stdio(false);
    207     ll T; cin >> T; while (T--) { tc(); }
    208     return 0;
    209 }
    210 ```
    211 
    212 **Rate The Problem!**
    213 
    214 * Heat
    215 * Mid
    216 * Horrendous
    217 * Didn't Solve
    218 
    219 #### [2060D - Subtract Min Sort](/contest/2060/problem/D "Codeforces Round 998 (Div. 3)")
    220 
    221 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")   
    222  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    223 
    224 **Solution**
    225 
    226 For clarity, let's denote $op_i$ as an operation performed on $a_i$ and $a_{i+1}$.
    227 
    228 Claim: if it is possible, then the sequence of operations $op_1,op_2,\ldots,op_{n-1}$ will sort the array.
    229 
    230 Proof: Let $b$ be any sequence of operations that will sort the array. Let's transform the sequence $b$ such that it becomes $[op_1,op_2,\ldots,op_{n-1}]$.
    231 
    232 First, let's note that an $op_i$ does nothing if $a_i=0$ or $a_{i+1}=0$. Additionally, after $op_i$, at least one of ${a_i,a_{i+1}}$ will become zero. Thus, we can remove all duplicates in $b$ without altering the result.
    233 
    234 Now, let $x$ be the largest number such that $op_x$ is in $b$. Since at least one of $a_x,a_{x+1}$ will be zero, operations must be performed such that each of $a_1,a_2,\ldots,a_{x-1}$ are zero. Let $S$ be the set of indices with $i \lt x$ such that $op_i$ is not in $b$. Note that we can simply append each operation in $S$ at the end of $b$ without altering the result, since all elements before $a_x$ are already zero.
    235 
    236 Our sequence of operations now contain a permutation of $op_1,op_2,\ldots,op_x$, and we have ensured that all of $a_1,a_2,\ldots,a_x=0$. Since the sequence is now sorted, we can in fact continue performing $op_{x+1},op_{x+2},\ldots,op_{n-1}$ in this order. Notice that this sequence of operations will keep our array sorted, as $op_y$ will make $a_y=0$ (since $a_y \lt a{y+1}$).
    237 
    238 Let's show that we can rearrange our operations such that $1$ comes first. There are two cases: either $op_1$ comes before $op_2$, or $op_2$ comes before $op_1$. In the first case, notice that no operation done before $op_1$ will impact either the value of $a_1$ or $a_2$, so rearranging such that $op_1$ comes first does not impact the final results. In the second case, notice that after $op_2$ is done, we must have $a_1=a_2$, as otherwise $op_1$ will not simultaneously make $a_1=a_2=0$. This implies that right before $op_2$ is performed, we must have $a_1+a_3=a_2$. Then, rearranging the operations such that $op_1$ comes first will not impact the final result.
    239 
    240 Using the same line of reasoning, we can make $op_2$ the second operation, then $op_3$, and so on. To solve the problem, we can simply simulate the operations in this order, and then check if the array is sorted at the end.
    241 
    242 Time Complexity : $O(n)$
    243 
    244 **Code (C++)**
    245 
    246 ```
    247 #include <bits/stdc++.h>
    248 using namespace std;
    249 using ll = long long;
    250 using vll = vector <ll>;
    251 using ii = pair <ll, ll>;
    252 using vii = vector <ii>;
    253 
    254 void tc () {
    255     ll n;
    256     cin >> n;
    257     vll ve(n);
    258     for (ll &i : ve) cin >> i;
    259     ll j = 0;
    260     for (ll i = 1; i < n; i++) {
    261         if (ve[i-1] > ve[i]) j = i;
    262     }
    263     if (j == 0) { // all done
    264         cout << "YES\n";
    265         return;
    266     }
    267     auto fop = [&](ll i) {
    268         ll minN = min(ve[i], ve[i+1]);
    269         ve[i] -= minN;
    270         ve[i+1] -= minN;
    271     };
    272     for (ll i = 0; i < j; i++) {
    273         fop(i);
    274     }
    275     cout << (is_sorted(ve.begin(), ve.end()) ? "YES" : "NO") << '\n';
    276 }
    277 
    278 int main () {
    279     cin.tie(nullptr) -> sync_with_stdio(false);
    280     ll T; cin >> T; while (T--) { tc(); }
    281     return 0;
    282 }
    283 ```
    284 
    285 **Rate The Problem!**
    286 
    287 * Heat
    288 * Mid
    289 * Horrendous
    290 * Didn't Solve
    291 
    292 #### [2060E - Graph Composition](/contest/2060/problem/E "Codeforces Round 998 (Div. 3)")
    293 
    294 Problem Credits: [Friedrich](/profile/Friedrich "Master Friedrich")   
    295  Analysis: [DivinePunishment](/profile/DivinePunishment "Expert DivinePunishment")
    296 
    297 **Solution**
    298 
    299 Let's solve the problem for each operation.
    300 
    301 First, consider the operation that removes an edge from $ F $. Divide $ G $ into its connected components and assign each vertex a component index. Then, for each edge in $ F $, if it connects vertices with different component indices, remove it and increment the operation count.
    302 
    303 This guarantees no path between $ x $ and $ y $ in $ F $ if there is none in $ G $. Next, to ensure a path exists between $ x $ and $ y $ in $ F $ if there is one in $ G $, we divide $ F $ into connected components. After removing excess edges, each component of $ F $ only contains vertices of the same component index. The number of operations needed now is the difference between the number of connected components in $ F $ and $ G $.
    304 
    305 All operations can be efficiently performed using DFS or DSU.
    306 
    307 **Code (C++)**
    308 
    309 ```
    310 #include <bits/stdc++.h>
    311 
    312 #define int long long
    313 #define pb emplace_back
    314 #define mp make_pair
    315 #define x first
    316 #define y second
    317 #define all(a) a.begin(), a.end()
    318 #define rall(a) a.rbegin(), a.rend()
    319 
    320 typedef long double ld;
    321 typedef long long ll;
    322 
    323 using namespace std;
    324 
    325 mt19937 rnd(time(nullptr));
    326 
    327 const int inf = 1e9;
    328 const int M = 1e9 + 7;
    329 const ld pi = atan2(0, -1);
    330 const ld eps = 1e-6;
    331 
    332 void Gdfs(int v, vector<vector<int>> &sl, vector<int> &col, int c){
    333     col[v] = c;
    334     for(int u: sl[v]){
    335         if(col[u] == 0){
    336             Gdfs(u, sl, col, c);
    337         }
    338     }
    339 }
    340 
    341 int Fdfs(int v, vector<vector<int>> &sl, vector<int> &col, vector<int> &old_col, int c){
    342     col[v] = c;
    343     int res = 0;
    344     for(int u: sl[v]){
    345         if(col[u] == 0){
    346             if(old_col[u] != c) res++;
    347             else res += Fdfs(u, sl, col, old_col, c);
    348         }
    349     }
    350     return res;
    351 }
    352 
    353 void read_con_list(vector<vector<int>> &sl, int m){
    354     for(int i = 0; i < m; ++i){
    355         int u, v;
    356         cin >> u >> v;
    357         sl[--u].emplace_back(--v);
    358         sl[v].emplace_back(u);
    359     }
    360 }
    361 
    362 void solve(int tc){
    363     int n, mf, mg;
    364     cin >> n >> mf >> mg;
    365     vector<vector<int>> fsl(n), gsl(n);
    366     read_con_list(fsl, mf);
    367     read_con_list(gsl, mg);
    368 
    369     vector<int> fcol(n), gcol(n);
    370     int ans = 0;
    371     for(int i = 0; i < n; ++i){
    372         if(gcol[i] == 0){
    373             Gdfs(i, gsl, gcol, i + 1);
    374         }
    375         if(fcol[i] == 0){
    376             ans += Fdfs(i, fsl, fcol, gcol, gcol[i]);
    377             if(gcol[i] < i + 1) ans++;
    378         }
    379     }
    380     cout << ans;
    381 }
    382 
    383 bool multi = true;
    384 
    385 signed main() {
    386     ios_base::sync_with_stdio(false);
    387     cin.tie(nullptr);
    388     cout.tie(nullptr);
    389 
    390     int t = 1;
    391     if (multi)cin >> t;
    392     for (int i = 1; i <= t; ++i) {
    393         solve(i);
    394         cout << "\n";
    395     }
    396     return 0;
    397 }
    398 ```
    399 
    400 **Rate The Problem!**
    401 
    402 * Heat
    403 * Mid
    404 * Horrendous
    405 * Didn't Solve
    406 
    407 #### [2060F - Multiplicative Arrays](/contest/2060/problem/F "Codeforces Round 998 (Div. 3)")
    408 
    409 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED"), [cry](/profile/cry "International Master cry")   
    410  Analysis: [-firefly-](/profile/-firefly- "Master -firefly-")
    411 
    412 **Hint 1**
    413 
    414 When $n$ is large, many of the array's elements will be $1$.
    415 
    416 **Hint 2**
    417 
    418 The number of non-$1$ elements can't be so large.
    419 
    420 **Hint 3**
    421 
    422 Try to precompute all arrays without $1$ and then use combinatorics.
    423 
    424 **Solution 1**
    425 
    426 The naive solution is to define $f_k(n)$ as the number of arrays containing $n$ elements with a product of $k$. We could then try to compute this by considering the last element of the array among the divisors of $k$, giving us:
    427 
    428 $ f_k(n)=\sum_{j|k}f_j(n-1), $
    429 
    430 with $f_k(1)=1$.
    431 
    432 The answers would then be $\sum_{i=1}^{n}f_1(i),\sum_{i=1}^{n}f_2(i),\dots,\sum_{i=1}^{n}f_k(i)$. However, this leads to an $O(nk\log k)$ solution, which exceeds our time constraints. We need to optimize this approach.
    433 
    434 We can prove that there are at most $16$ non-$1$ elements in our arrays. This is because:
    435 
    436 * The prime factorization of $k=p_1p_2\cdots p_t$ divides $k$ into the most non-$1$ elements.
    437 * With $17$ non-$1$ elements, the smallest possible value would be $k=2^{17}=131072 \gt 10^5$.
    438 
    439 Based on this observation, we can define our dynamic programming state as:
    440 
    441 * Let $dp[i][j]$ represent the number of arrays with product $i$ containing only $j$ **non-$1$** elements.
    442 * The recurrence relation becomes: $dp[i][j]=\sum_{p|i,p \gt 1}dp[\frac{i}{p}][j-1]$.
    443 * Base case: $dp[i][1]=1$ for $i \gt 1$.
    444 
    445 This computation has a time complexity of $O(k\log^2k)$, as we perform $\sum_{j=1}^{k}d(j)=O(k\log{k})$ additions for each $i$.
    446 
    447 To calculate $f_k(n)$, we:
    448 
    449 1. Enumerate the number of non-$1$ elements from $1$ to $16$.
    450 2. For $j$ non-$1$ elements in the array:
    451 
    452 * We have $n-j$ elements that are $1$.
    453 * We need to choose $j$ positions for non-$1$ elements.
    454 * Fill these positions with $dp[k][j]$ possible sequences.
    455 
    456 This gives us:
    457 
    458 $ f_k(n)=\sum_{j=1}^{16}\binom{n}{j}dp[k][j]. $
    459 
    460 Therefore:
    461 
    462 $ \begin{align*} &\sum_{i=1}^{n}f_k(n)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{16}\binom{i}{j}dp[k][j]\\ =&\sum_{j=1}^{16}\left(dp[k][j]\sum_{i=1}^{n}\binom{i}{j}\right)\\ =&\sum_{j=1}^{16}\binom{n+1}{j+1}dp[k][j]. \end{align*} $
    463 
    464 Note that $\sum_{i=1}^{n}\binom{i}{j} = \binom{n+1}{j+1}$ is given by the [Hockey Stick Identity](https://en.wikipedia.org/wiki/Hockey-stick_identity).
    465 
    466 Each answer can be calculated in $O(\log^2k)$ time, giving an overall time complexity of $O(k\log^2k)$.
    467 
    468 **Solution 2**
    469 
    470 Let's revisit the naive approach and define $S_k(n)=\sum_{i=1}^{n}f_{k}(n)$ as our answers. We can observe:
    471 
    472 $ \begin{align} f_{k}(n)&=\sum_{j|k}f_j(n-1)\nonumber\\ \Leftrightarrow f_{k}(n)-f_{k}(n-1)&=\sum_{j|k,j \lt k}f_j(n-1). \end{align} $
    473 
    474 Accumulating Formula $(1)$ yields:
    475 
    476 $ \begin{align} &&\sum_{i=2}^{n}\left(f_{k}(i)-f_{k}(i-1)\right)&=\sum_{i=2}^{n}\sum_{j|k,j \lt k}f_j(i-1)\nonumber\\ &\Leftrightarrow& f_{k}(n)-f_{k}(1)&=\sum_{j|k,j \lt k}\sum_{i=1}^{n-1}f_{j}(i)\nonumber\\ &\Leftrightarrow& f_{k}(n)&=\sum_{j|k,j \lt k}S_j(n-1)+1. \end{align} $
    477 
    478 By induction, we can prove that both $f_{k}(n)$ and $S_k(n)$ are polynomials. Let's denote:
    479 
    480 * Degree of $f_k(n)$ as $p(k)$.
    481 * Degree of $S_k(n)$ as $q(k)$.
    482 
    483 From the definition of $S_k(n)$, we have $q(k)=p(k)+1$. Formula $(2)$ gives us:
    484 
    485 $ p(k)=\max_{j|k,j \lt k}q(k)=\max_{j|k,j \lt k}p(j)+1, $
    486 
    487 with $p(1)=0$. By induction, we can show that $p(k)$ equals the number of primes in $k$'s prime factorization. Therefore, $p(k)\le16$ and $q(k)\le17$.
    488 
    489 Since $q(k)$ doesn't exceed $17$, we can:
    490 
    491 1. Precompute $S_k(1),S_k(2),S_k(3),\dots,S_k(18)$.
    492 2. Use [Lagrange Interpolation](https://codeforces.com/blog/entry/82953) to compute any $S_k(n)$.
    493 
    494 This also yields an $O(k\log^2k)$ time complexity.
    495 
    496 **Code (C#)**
    497 
    498 ```
    499 using System;
    500 using System.Collections.Generic;
    501 using System.ComponentModel;
    502 using System.Linq;
    503 using System.Runtime.Serialization.Json;
    504 using System.Text;
    505 using System.Threading.Tasks;
    506 using TemplateF;
    507 
    508 #if !PROBLEM
    509 SolutionF a = new();
    510 a.Solve();
    511 #endif
    512 
    513 namespace TemplateF
    514 {
    515     internal class SolutionF
    516     {
    517         private readonly StreamReader sr = new(Console.OpenStandardInput());
    518         private T Read<T>()
    519             where T : struct, IConvertible
    520         {
    521             char c;
    522             dynamic res = default(T);
    523             dynamic sign = 1;
    524             while (!sr.EndOfStream && char.IsWhiteSpace((char)sr.Peek())) sr.Read();
    525             if (!sr.EndOfStream && (char)sr.Peek() == '-')
    526             {
    527                 sr.Read();
    528                 sign = -1;
    529             }
    530             while (!sr.EndOfStream && char.IsDigit((char)sr.Peek()))
    531             {
    532                 c = (char)sr.Read();
    533                 res = res * 10 + c - '0';
    534             }
    535             return res * sign;
    536         }
    537 
    538         private T[] ReadArray<T>(int n)
    539             where T : struct, IConvertible
    540         {
    541             T[] arr = new T[n];
    542             for (int i = 0; i < n; ++i) arr[i] = Read<T>();
    543             return arr;
    544         }
    545 
    546         public void Solve()
    547         {
    548             StringBuilder output = new();
    549             const int maxk = 100000, mod = 998244353, bw = 20;
    550             List<int>[] d = new List<int>[maxk + 1];
    551             for (int i = 1; i <= maxk; ++i) d[i] = new() { 1 };
    552             for (int i = 2; i <= maxk; ++i) {
    553                 for (int j = i; j <= maxk; j += i) d[j].Add(i);
    554             }
    555             int[,] dp = new int[bw + 1, maxk + 1], S = new int[bw + 1, maxk + 1];
    556             for (int k = 1; k <= maxk; ++k) dp[1, k] = S[1, k] = 1;
    557             for (int i = 2; i <= bw; ++i) {
    558                 for (int j = 1; j <= maxk; ++j) {
    559                     foreach (var k in d[j]) {
    560                         dp[i, j] += dp[i - 1, k];
    561                         dp[i, j] %= mod;
    562                     }
    563                     S[i, j] = (S[i - 1, j] + dp[i, j]) % mod;
    564                 }
    565             }
    566             int T = Read<int>();
    567             while (T-- > 0)
    568             {
    569                 int k = Read<int>(), n = Read<int>();
    570                 if (n <= bw) {
    571                     for (int j = 1; j <= k; ++j) output.Append(S[n, j]).Append(' ');
    572                 } else {
    573                     int _k = k;
    574                     for (k = 1; k <= _k; ++k)  {
    575                         long ans = 0;
    576                         for (int i = 1; i <= bw; ++i) {
    577                             long t = S[i, k];
    578                             for (int j = 1; j <= bw; ++j) {
    579                                 if (j == i) continue;
    580                                 t *= n - j;
    581                                 t %= mod;
    582                                 t *= Inv((mod + i - j) % mod, mod);
    583                                 t %= mod;
    584                             }
    585                             ans = (ans + t) % mod;
    586                         }
    587                         output.Append(ans).Append(' ');
    588                     }
    589                 }
    590                 output.AppendLine();
    591             }
    592             Console.Write(output.ToString());
    593         }
    594         public static long Inv(long a, long Mod) {
    595             long u = 0, v = 1, m = Mod;
    596             while (a > 0) {
    597                 long t = m / a;
    598                 m -= t * a; (a, m) = (m, a);
    599                 u -= t * v; (u, v) = (v, u);
    600             }
    601             return (u % Mod + Mod) % Mod;
    602         }
    603     }
    604 }
    605 ```
    606 
    607 **Rate The Problem!**
    608 
    609 * Heat
    610 * Mid
    611 * Horrendous
    612 * Didn't Solve
    613 
    614 #### [2060G - Bugged Sort](/contest/2060/problem/G "Codeforces Round 998 (Div. 3)")
    615 
    616 Problem Credits: [chromate00](/profile/chromate00 "Expert chromate00")   
    617  Analysis: [macaquedev](/profile/macaquedev "Expert macaquedev")
    618 
    619 **Hint 1**
    620 
    621 Consider $(a_i, b_i)$ as the $i$-th pair. Can two elements ever become unpaired?
    622 
    623 **Answer**
    624 
    625 No. Every operation keeps the pairs intact. The best way to think about the operation is like this:
    626 
    627 1. Swap the pairs at index $i$ and index $j$.
    628 2. Flip each pair (swap $a_i$ with $b_i$, and $a_j$ with $b_j$).
    629 
    630 **Hint 2**
    631 
    632 The operations allow us to swap two pairs, but it also results in both of them getting flipped. Is there any way to swap two pairs *without* flipping anything?
    633 
    634 **Answer**
    635 
    636 It turns out there is, and there always is, because $n \geq 3$. To swap pairs $i$ and $j$, follow this procedure:
    637 
    638 1. Pick any index $k$, where $k \ne i$ and $k \ne j$.
    639 2. Do the operation on $i$ and $k$.
    640 3. Do the operation on $j$ and $k$.
    641 4. Finally, do the operation on $i$ and $k$ again. This results in the pair at index $k$ being unchanged, and the pairs at $i$ and $j$ simply being swapped.
    642 
    643 ![](/predownloaded/5b/1d/5b1d12611f7a23c2afe87588dc7ba673fe994114.png)
    644 
    645 **Hint 3**
    646 
    647 Can you flip two pairs without swapping them?
    648 
    649 **Answer**
    650 
    651 Yes. Just perform the operation on pairs $i$ and $j$, and then follow the procedure from Hint 2, and you are effectively swapping, then "swapping and flipping", therefore the final result is simply a flip of two pairs.
    652 
    653 ![](/predownloaded/9f/d9/9fd9532ea99dea2d7d2b8e764120f67f506f20f3.png)
    654 
    655 **Hint 4**
    656 
    657 Can you flip one pair on its own?
    658 
    659 **Answer**
    660 
    661 No, this is not possible due to the parity invariant. The operation involves performing two flips at the same time, which means that it is impossible to end up in a situation where the number of flips is odd.
    662 
    663 **Solution**
    664 
    665 Read the hints first.
    666 
    667 **Key observation:**
    668 
    669 In the final solution, the pairs must be sorted in increasing order of $\min(a_i, b_i)$. We prove this by contradiction. Suppose there exists a pair $(a_i, b_i)$, where $a_i \lt b_i$ and $a_i$ is smaller than the minimum element in the previous pair. In this case, it becomes impossible to place this pair after the previous one, as $a_i$ would always be smaller than the preceding element, regardless of orientation.
    670 
    671 Since all $a_i$ and $b_i$ are distinct, there is exactly one valid final ordering of the pairs. Moreover, this ordering is always reachable because we previously proved that any two pairs can be swapped without flipping their elements. Since swapping any two items in an array an arbitrary number of times allows for sorting by definition, we can sort the pairs in this order. Thus, the solution is to initially sort the pairs based on $\min(a_i, b_i)$.
    672 
    673 **Solution:**
    674 
    675 The problem simplifies to determining whether flipping pairs allows sorting. We can solve this using dynamic programming (DP), defined as follows:
    676 
    677 $dp[1][i] = 1$ if it's possible to sort up and including pair $i$ using an even number of flips, where pair $i$ is not flipped.   
    678  $dp[2][i] = 1$ if it's possible to sort up and including pair $i$ using an even number of flips, where pair $i$ is flipped.  
    679  $dp[3][i] = 1$ if it's possible to sort up and including pair $i$ using an odd number of flips, where pair $i$ is not flipped.  
    680  $dp[4][i] = 1$ if it's possible to sort up and including pair $i$ using an odd number of flips, where pair $i$ is flipped.
    681 
    682 The base cases are as follows:
    683 
    684 $dp[1][1] = 1$, because this represents the state where the first pair is not flipped, resulting in zero flips (which is even)   
    685  $dp[4][1] = 1$, because this represents the state where the first pair is flipped, resulting in one flip (which is odd).
    686 
    687 There are eight possible transitions, as you can reach each of the four states from two previous states: you either choose to flip the current element or you don't.
    688 
    689 The final answer is $dp[1][n]$ $\texttt{OR}$ $dp[2][n]$, because by Hints 3 and 4, we can only reach states where an even number of pairs are flipped from the starting position.
    690 
    691 **Code (C++)**
    692 
    693 ```
    694 #include <bits/stdc++.h>
    695 using namespace std;
    696 #define F0R(i, n) for (int i = 0; i < n; i++)
    697 #define FOR(i, m, n) for (int i = m; i < n; i++)
    698 #define print pair<int, int>
    699 #define vp vector<print>
    700 #define ALL(x) (x).begin(), (x).end()
    701 
    702 void solve()
    703 {
    704     int n;
    705     cin >> n;
    706     vp pairs(n);
    707     F0R(i, n)
    708     {
    709         cin >> pairs[i].first;
    710     }
    711     F0R(i, n)
    712     {
    713         cin >> pairs[i].second;
    714     }
    715 
    716     sort(ALL(pairs), [](print a, print b)
    717          { return min(a.first, a.second) < min(b.first, b.second); });
    718 
    719     vector<vector<int>> dp(4, vector<int>(n, 0));
    720     dp[0][0] = 1;
    721     dp[3][0] = 1;
    722     FOR(i, 1, n)
    723     {
    724         if (pairs[i - 1].first < pairs[i].first and pairs[i - 1].second < pairs[i].second)
    725         {
    726             dp[0][i] |= dp[0][i - 1];
    727             dp[1][i] |= dp[1][i - 1];
    728             dp[2][i] |= dp[3][i - 1];
    729             dp[3][i] |= dp[2][i - 1];
    730         }
    731         if (pairs[i - 1].first < pairs[i].second and pairs[i - 1].second < pairs[i].first)
    732         {
    733             dp[0][i] |= dp[2][i - 1];
    734             dp[1][i] |= dp[3][i - 1];
    735             dp[2][i] |= dp[1][i - 1];
    736             dp[3][i] |= dp[0][i - 1];
    737         }
    738     }
    739     cout << ((dp[0][n - 1] | dp[2][n - 1]) ? "YES" : "NO") << endl;
    740 }
    741 
    742 signed main()
    743 {
    744     int tests;
    745     cin >> tests;
    746     F0R(test, tests)
    747     {
    748         solve();
    749     }
    750 
    751     return 0;
    752 }
    753 ```
    754 
    755 **Rate The Problem!**
    756 
    757 * Heat
    758 * Mid
    759 * Horrendous
    760 * Didn't Solve