codeforces-scrape

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

1984.md (39522B)


      1 Source: https://codeforces.com/blog/entry/130252
      2 
      3 Thank you for participating! We put a lot of effort into this contest. Special thanks to [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") for contributing to these problems.
      4 
      5 **Rating Predictions**
      6 
      7 | Person | A | B | C1 | C2 | D | E | F | G | H |
      8 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      9 | [null_awe](/profile/null_awe "Grandmaster null_awe") | 800 | 1000 | 1200 | 1700 | 2200 | 2400 | 2500 | 2900 | 3400 |
     10 | [buffering](/profile/buffering "Expert buffering") | 800 | 1000 | 1300 | 1800 | 2300 | 2400 | 2600 | 3100 | 3500 |
     11 | [redpanda](/profile/redpanda "Expert redpanda") | 800 | 1100 | 1200 | 1800 |  |  |  |  |  |
     12 | [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") | 800 | 1000 | 1200 | 1600 | 2200 | 2500 | 2500 | 3100 | 3400 |
     13 | [bronze_coder](/profile/bronze_coder "Grandmaster bronze_coder") | 800 | 1000 | 1600 | 1800 | 2400 |  |  | 2700 | 3500 |
     14 | [awesomeguy856](/profile/awesomeguy856 "Master awesomeguy856") | 800 | 1100 | 1300 | 1700 | 2200 | 2300 | 2600 |  |  |
     15 | [flamestorm](/profile/flamestorm "Master flamestorm") | 800 | 1100 | 1200 | 1600 | 2200 | 2400 | 2500 | 3100 | 3200 |
     16 | [Ste](/profile/Ste "Master Ste") | 800 | 1100 | 1000 | 1600 | 2000 | 2400 | 2400 |  |  |
     17 
     18 |  | A | B | C1 | C2 | D | E | F | G | H |
     19 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     20 | Average | 800 | 1050 | 1250 | 1700 | 2214 | 2400 | 2516 | 2980 | 3400 |
     21 | Actual | 800 | 1100 | 1300 | 1700 | 2000 | 2400 | 2500 | 3200 | 3300 |
     22 
     23 Also, check out this video editorial for problems A through C2 by one of our testers! <https://www.youtube.com/watch?v=hS8Z3k57f6Q>
     24 
     25 #### Solutions
     26 
     27 ##### [1984A - Strange Splitting](/contest/1984/problem/A "Codeforces Global Round 26")
     28 
     29 Problem Credits: [buffering](/profile/buffering "Expert buffering")   
     30 Analysis: [buffering](/profile/buffering "Expert buffering")
     31 
     32 **Hint 1**
     33 
     34 When is it impossible?
     35 
     36 **Answer**
     37 
     38 When $a = [x, x \dots x]$ for some $x$.
     39 
     40 **Hint 2**
     41 
     42 Only color one element red to make the range $0$. Which one do you pick to make the blue range different?
     43 
     44 **Solution**
     45 
     46 Read the hints.
     47 
     48 It is impossible to color the array when all the elements are the same, because the range for the red and blue elements will always be $0$.
     49 
     50 Otherwise, notice there will always be at least $2$ distinct values in the array. This means there is a way to get a positive range for the blue elements, by taking the maximum value and the minimum value and coloring them blue. This works because $n \geq 3$, so there is at least one element left.
     51 
     52 Since we can get a positive range, we can then try to get the red elements to have a range of $0$, by coloring exactly one value red. So, we can color any $a_i$ for $2 \leq i \leq n - 1$ red since it will not affect the positive range we constructed for the blue elements. For simplicity sake, our solution chooses $i = 2$. Then, the remaining elements can be colored blue.
     53 
     54 Therefore, our final solution is to check if it is impossible, or color $a_2$ red and the rest blue.
     55 
     56 **Code (C++)**
     57 
     58 ```
     59 #include <iostream>
     60 using namespace std;
     61 int main(){
     62     int T; cin >> T;
     63 
     64     while (T--) {
     65 
     66         int n; cin >> n;
     67 
     68         vector<int> a(n);
     69         for (int i = 0; i < n; i++) {
     70             cin >> a[i];
     71         }
     72 
     73         if (a[0] == a[n - 1]) {
     74             cout << "NO" << "\n";
     75         }
     76         else {
     77             cout << "YES" << "\n";
     78             string s(n, 'R'); 
     79             s[1] = 'B';
     80             cout << s << "\n";
     81 
     82         }
     83 
     84         
     85     }
     86 }
     87 ```
     88 
     89 ##### [1984B - Large Addition](/contest/1984/problem/B "Codeforces Global Round 26")
     90 
     91 Problem Credits: [flamestorm](/profile/flamestorm "Master flamestorm")   
     92 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe")
     93 
     94 Solution 1
     95 
     96 **Hint 1**
     97 
     98 What must the first (largest) digit be?
     99 
    100 **Hint 2**
    101 
    102 What must the other non-unit digits be?
    103 
    104 **Hint 3**
    105 
    106 What must the last digit be?
    107 
    108 **Solution**
    109 
    110 Because every digit is large, every two digits being added together will carry to the next digit. The two addends have the same length, so the sum must be one greater in length, with the largest digit equal to $1$.
    111 
    112 For all other digits except for the units digit, we have the value to be the sum of two large digits, plus $1$ being carried over from the previous column. This makes the acceptable range of values be from $1$ to $9$, inclusive.
    113 
    114 For the units digit, there is no previous column to carry over a $1$, so the acceptable range of values is from $0$ to $8$, inclusive.
    115 
    116 **Code (C++)**
    117 
    118 ```
    119 #include <iostream>
    120 using namespace std;
    121  
    122 #define ll long long
    123  
    124 void solve() {
    125   ll n; cin >> n;
    126   n = n - n % 10 + (n % 10 + 1) % 10;
    127   while (n > 9) {
    128     if (n % 10 == 0) {
    129       cout << "NO\n";
    130       return;
    131     }
    132     n /= 10;
    133   }
    134   cout << (n == 1 ? "YES\n" : "NO\n");
    135 }
    136  
    137 int main() {
    138   ios_base::sync_with_stdio(false); cin.tie(NULL);
    139   int t; cin >> t;
    140   for (int i = 0; i < t; ++i) solve();
    141   return 0;
    142 }
    143 ```
    144 
    145 ##### [1984C1 - Magnitude (Easy Version)](/contest/1984/problem/C1 "Codeforces Global Round 26") and [1984C2 - Magnitude (Hard Version)](/contest/1984/problem/C2 "Codeforces Global Round 26")
    146 
    147 Problem Credits: [buffering](/profile/buffering "Expert buffering")   
    148 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe")
    149 
    150 **Hint 1**
    151 
    152 How many times do we need to pick option $2$?
    153 
    154 **Hint 2**
    155 
    156 We only need to pick it once. How can we calculate the final value for every position we can pick?
    157 
    158 **Solution (Easy Version)**
    159 
    160 We only need to pick option $2$ once. Why? Assume we picked option $2$ more than once, and consider the last two times it was picked. Both of these must occur when $c + a_i$ is negative, otherwise there is no reason to pick option $2$ over option $1$. Thus, if we chose option $1$ the first of these times instead of option $2$, that would cause the value of $c$ before the second operation to decrease. Because it was negative, this increases the magnitude, and thus it was more optimal to choose option $1$ for the first operation.
    161 
    162 Because we only need to use option $2$ once, we can brute force where we use that operation and compute the final value of $c$ with prefix sums.
    163 
    164 **Solution (Hard Version)**
    165 
    166 Read the solution to the easy version first.
    167 
    168 Let's think a bit more. Where do we actually end up using option $2$? We only use option $2$ when our prefix sum up to this point is minimum in the whole array.
    169 
    170 Now, focus on each individual "important" use of option $2$ (where it actually makes a difference from option $1$), Let's say it is done at index $i$. Let's consider indices before. Since the operation at index $i$ is the only important option $2$, any option $2$'s we use before must not have been different from option $1$ (meaning that the value of $c + a_j$ has to be non-negative). Thus, we have the choice of using option $2$ or option $1$ at any index $j \lt i$ where the prefix sum is non-negative. Let's say there exists $x$ unique values of $j$.
    171 
    172 Now, let's consider indices after. Since index $i$ is at a minimum prefix sum, that guarantees that all indices after will never have a lower value of $c$ than what $c$ is after doing the operation at index $i$. Thus, since we use option 2 at index $i$, we can use any of the two options moving forward. Thus, any index $j \gt i$ has two choices on which option to pick. Let's say there exists $y$ unique values of $j$.
    173 
    174 The contribution of index $i$ to the answer is then $2^{x + y}$.
    175 
    176 Special case: the prefix sum never becomes negative. What is the answer then?
    177 
    178 **Code (C++)**
    179 
    180 **Easy Version**
    181 
    182 ```
    183 #include <iostream>
    184 #include <vector>
    185 #include <climits>
    186 using namespace std;
    187  
    188 #define ll long long
    189  
    190 void solve() {
    191   int n; cin >> n;
    192   vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];
    193   ll sum = 0, mn = 0;
    194   for (int i = 0; i < n; ++i) sum += arr[i], mn = min(mn, sum);
    195   cout << sum - 2 * mn << '\n';
    196 }
    197  
    198 int main() {
    199   ios_base::sync_with_stdio(false); cin.tie(NULL);
    200   int t; cin >> t;
    201   for (int i = 0; i < t; ++i) solve();
    202   return 0;
    203 }
    204 ```
    205 
    206 **Hard Version**
    207 
    208 ```
    209 #include <iostream>
    210 #include <vector>
    211 #include <climits>
    212 using namespace std;
    213  
    214 #define ll long long
    215  
    216 const ll MAX_N = 400001;
    217 const ll MOD = 998244353;
    218  
    219 vector<ll> p2(MAX_N);
    220  
    221 void solve() {
    222   int n; cin >> n;
    223   vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];
    224   ll sum = 0, mn = 0, ans = 0, abses = 0;
    225   for (int i = 0; i < n; ++i) sum += arr[i], mn = min(mn, sum);
    226   if (mn == 0) {
    227       cout << p2[n] << '\n';
    228       return;
    229   }
    230   sum = 0;
    231   for (int i = 0; i < n; ++i) {
    232     sum += arr[i];
    233     if (sum == mn) {
    234       ans = (ans + p2[n - i - 1 + abses]) % MOD;
    235     }
    236     if (sum >= 0) ++abses;
    237   }
    238   cout << ans << '\n';
    239 }
    240  
    241 int main() {
    242   ios_base::sync_with_stdio(false); cin.tie(NULL);
    243   p2[0] = 1;
    244   for (int i = 1; i < MAX_N; ++i) p2[i] = 2 * p2[i - 1] % MOD;
    245   int t; cin >> t;
    246   for (int i = 0; i < t; ++i) solve();
    247   return 0;
    248 }
    249 ```
    250 
    251 #### [1984D - ''a'' String Problem](/contest/1984/problem/D "Codeforces Global Round 26")
    252 
    253 Problem Credits: [le0n](/profile/le0n "International Grandmaster le0n")   
    254 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe")
    255 
    256 **Hint 1**
    257 
    258 What does $t$ have to include?
    259 
    260 **Solution**
    261 
    262 Special case: the string consists of only "$\texttt{a}$", then answer is $n - 1$.
    263 
    264 Otherwise, $t$ has to contain a character that is not "$\texttt{a}$". Let's consider one approach of counting. Let's force all $t$ to start with the first non-a character, and see how many work.
    265 
    266 To see if one of these strings $t$ will work, we can start with $i = 0$. As long as $i$ does not point to the end of the string, we can find the next non-a character in $s$, and then see if the next $|t|$ characters in $s$ matches $t$. The last check mentioned can be done through hashing or using the Z-function. If it doesn't, this value of $t$ doesn't work. Otherwise, we update $i$ to the new current position and continue checking.
    267 
    268 Now, if we find a string $t$ that does work, we need to count its contribution to the answer. We can just add $1$, but obviously not all working $t$ will start with a non-a character. Instead, we can find the minimum unused "$\texttt{a}$"s before all of the substrings equal to $t$ (call this $m$), and the current $t$ will be able to extend out up to $m$ "$\texttt{a}$"s at the beginning of the string. Thus, the contribution is $m + 1$ to the answer.
    269 
    270 How fast is this? Because we are checking at most one string $t$ of each length, and the check itself can be made to take $O(\frac{n}{|t|})$, we have a total time complexity of $O(n\log{n})$ due to harmonic sums.
    271 
    272 **Code (C++)**
    273 
    274 ```
    275 #include <iostream>
    276 #include <vector>
    277 #include <climits>
    278 #include <set>
    279 using namespace std;
    280  
    281 #define ll long long
    282  
    283 vector<int> z_function(string s) {
    284   int n = s.size();
    285   vector<int> z(n);
    286   int l = 0, r = 0;
    287   for(int i = 1; i < n; ++i) {
    288     if (i < r) z[i] = min(r - i, z[i - l]);
    289     while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    290     if (i + z[i] > r) l = i, r = i + z[i];
    291   }
    292   return z;
    293 }
    294  
    295 void solve() {
    296   int n; // cin >> n;
    297   string s; cin >> s;
    298   n = s.length();
    299   vector<int> nona(n, n);
    300   for (int i = n - 1; i >= 0; --i) {
    301     if (s[i] != 'a') nona[i] = i;
    302     else if (i + 1 < n) nona[i] = nona[i + 1];
    303   }
    304   if (nona[0] == n) {
    305     cout << n - 1 << '\n';
    306     return;
    307   }
    308   string s2 = "";
    309   int i1 = nona[0];
    310   for (int i = i1; i < n; ++i) s2 += s[i];
    311   vector<int> z = z_function(s2);
    312   ll ans = 0;
    313   for (int len = 1; i1 + len <= n; ++len) {
    314     int cur = i1 + len;
    315     int mn = i1;
    316     bool works = true;
    317     while (cur < n) {
    318       if (nona[cur] == n) break;
    319       int bt = nona[cur] - cur;
    320       mn = min(mn, bt);
    321       cur += bt;
    322       if (z[cur - i1] < len) {
    323         works = false;
    324         break;
    325       }
    326       cur += len;
    327     }
    328     if (works) ans += mn + 1;
    329   }
    330   cout << ans << '\n';
    331 }
    332  
    333 int main() {
    334   int t; cin >> t;
    335   for (int i = 0; i < t; ++i) solve();
    336   return 0;
    337 }
    338 ```
    339 
    340 #### [1984E - Shuffle](/contest/1984/problem/E "Codeforces Global Round 26")
    341 
    342 Problem Credits: [null_awe](/profile/null_awe "Grandmaster null_awe"), thanks to [wavelets](/profile/wavelets "Grandmaster wavelets") for helping with brainstorming   
    343 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe")
    344 
    345 **Solution**
    346 
    347 Excluding the root, the maximum number of leaves we have is the maximum independent set (MIS) of the rest of the tree. Why? First of all, after rooting tree $T_2$, no two adjacent nodes can both be leaves. This is because, no matter which one you choose to add to $T_2$ first, it must be the ancestor of the other one. Thus, the first chosen node will not be a leaf. Furthermore, any chosen MIS of nodes can all become leaves. This is because we can essentially choose to add all of the nodes not in the MIS first to the tree, leaving all of the remaining nodes to be childless nodes, making them all leaves.
    348 
    349 To find the answer, we want to find the maximum MIS of all subtrees that are missing one leaf. The answer will be one greater than this maximum MIS due to the root of $T_2$ being also a leaf.
    350 
    351 There are multiple dynamic programming approaches to compute this efficiently, including rerooting and performing dynamic programming on tree edges.
    352 
    353 Time complexity: $O(n)$ or $O(n \log{n})$, depending on implementation.
    354 
    355 **Code (C++)**
    356 
    357 ```
    358 #include <iostream>
    359 #include <vector>
    360 #include <map>
    361 using namespace std;
    362  
    363 #define pii pair<int, int>
    364  
    365 int n;
    366 vector<vector<int>> adj;
    367 vector<pii> edges;
    368 map<pii, int> mp;
    369  
    370 vector<vector<int>> dp;
    371 vector<vector<int>> from;
    372 vector<int> miss;
    373  
    374 void dfs(int e) {
    375   if (dp[0][e] >= 0 || dp[1][e] >= 0) return;
    376   int p = edges[e].first, v = edges[e].second;
    377   dp[0][e] = 0, dp[1][e] = 1;
    378   if (miss[v] < 0) {
    379     for (int u : adj[v]) {
    380       if (u == p) continue;
    381       int ne = mp[{v, u}];
    382       dfs(ne);
    383       from[0][v] += max(dp[1][ne], dp[0][ne]);
    384       from[1][v] += dp[0][ne];
    385     }
    386     miss[v] = p;
    387   }
    388   if (miss[v] != p && miss[v] != n) {
    389     int ne = mp[{v, miss[v]}];
    390     dfs(ne);
    391     from[0][v] += max(dp[1][ne], dp[0][ne]);
    392     from[1][v] += dp[0][ne];
    393     miss[v] = n;
    394   }
    395   if (miss[v] == n) {
    396     int nne = mp[{v, p}];
    397     dp[0][e] += from[0][v] - max(dp[1][nne], dp[0][nne]);
    398     dp[1][e] += from[1][v] - dp[0][nne];
    399   } else if (miss[v] == p) {
    400     dp[0][e] += from[0][v];
    401     dp[1][e] += from[1][v];
    402   }
    403 }
    404  
    405 void solve() {
    406   cin >> n;
    407   adj.clear(), edges.clear();
    408   adj.resize(n), edges.resize(2 * n - 2);
    409   for (int i = 0; i < n - 1; ++i) {
    410     int a, b; cin >> a >> b; --a, --b;
    411     adj[a].push_back(b);
    412     adj[b].push_back(a);
    413     edges[2 * i] = {a, b};
    414     edges[2 * i + 1] = {b, a};
    415     mp[{a, b}] = 2 * i;
    416     mp[{b, a}] = 2 * i + 1;
    417   }
    418   from = vector<vector<int>>(2, vector<int>(n));
    419   miss = vector<int>(n, -1);
    420   dp = vector<vector<int>>(2, vector<int>(2 * n - 2, -1));
    421   for (int i = 0; i < 2 * n - 2; ++i) dfs(i);
    422   int ans = 0;
    423   for (int i = 0; i < n; ++i) {
    424     if (adj[i].size() != 1) continue;
    425     int e = mp[{i, adj[i][0]}];
    426     ans = max(ans, 1 + max(dp[0][e], dp[1][e]));
    427   }
    428   cout << ans << '\n';
    429 }
    430  
    431 int main() {
    432   ios_base::sync_with_stdio(false); cin.tie(NULL);
    433   int t; cin >> t;
    434   for (int i = 0; i < t; ++i) solve();
    435   return 0;
    436 }
    437 ```
    438 
    439 #### [1984F - Reconstruction](/contest/1984/problem/F "Codeforces Global Round 26")
    440 
    441 Problem Credits: [buffering](/profile/buffering "Expert buffering")   
    442 Analysis: [buffering](/profile/buffering "Expert buffering")
    443 
    444 **Hint 1**
    445 
    446 Solve for no question marks in the string first.
    447 
    448 **Hint 2**
    449 
    450 Add a $0$ on both sides of $a$ and $b$, and add a $\texttt{P}$ before the start of the string and a $\texttt{S}$ after the string. Now you are guaranteed to have a $\texttt{PS}$ somewhere in the string. How does this help?
    451 
    452 **Answer**
    453 
    454 You know the sum of the array.
    455 
    456 **Hint 3**
    457 
    458 Look at adjacent elements in $b$, and its corresponding characters in the string, and see if you can determine anything about $a$.
    459 
    460 **Hint 4**
    461 
    462 Go back to the original problem, with question marks. We do not know the sum now, but how many possible ones can there be?
    463 
    464 **Solution**
    465 
    466 How to solve with no question marks?
    467 
    468 To simplify things, let's extend all arrays both ways by 1 element. In array $a$ and $b$, we can keep both values at $0$, and in the string $s$, we can assign the left value to "$\texttt{P}$" and the right value to "$\texttt{S}$" (the other values will still be satisfied -- why?)
    469 
    470 Now, somewhere within the string, we are guaranteed to see the combination "$\texttt{PS}$" because we now have a string that starts with "$\texttt{P}$" and ends with "$\texttt{S}$", therefore it must transition somewhere in between.
    471 
    472 Notice, if we add the values in $b$ of the "$\texttt{PS}$", we can gather the sum of the array.
    473 
    474 Now, solving becomes simpler. We can focus on adjacent elements in the array. Say we are currently examining indices $i$ and $i + 1$. There are four cases:
    475 
    476 1. We are currently at a "$\texttt{PP}$". We then know $b_i + a_{i+1} = b_{i+1}$, so $a_{i+1}$ is now known.
    477 2. We are currently at a "$\texttt{PS}$". Again, this must be the sum. All we have to do here is check that our sum is correct.
    478 3. We are currently at an "$\texttt{SP}$". Here, we have $b_{i} + b_{i+1} - SUM = a_i + a_{i+1}$ (why?). Our left side is known, and the only requirement on the right side is that both $a_i$ and $a_{i+1}$ have to have a magnitude of at most $m$. Thus, to make their maximum magnitude as small as possible, we make them as close as possible to each other. If the left side is $x$, we assign $a_i = \text{floor}(x / 2)$, and $a_{i+1} = x - a_i$.
    479 4. We are currently at an "$\texttt{SS}$". This is similar to the first case, as we know that $b_i = a_i + b_{i+1}$. Thus, $a[i]$ will be known.
    480 
    481 If $a_i$ is always possible, then we know our answer exists.
    482 
    483 Thus, this solves a version without question marks. For the version with question marks, we can only try to guess what the sum of the entire array is, since we don't know where "$\texttt{PS}$" might be for sure every time. There are only $n$ possibilities — the sum of every pair of adjacent numbers in $b$.
    484 
    485 For every possibility, we can run a `dp[i][j]` where we are currently at index $i$ and the last character within "$\texttt{P}$" and "$\texttt{S}$" in string $s$ used was $j$. This dynamic programming will run in linear time because of constant-time transitions and linear amount of states. Note that this is only possible due to the independent nature of adjacent pairs as described earlier.
    486 
    487 With this DP, we can calculate how many paths are possible, adding to our answer.
    488 
    489 Time complexity $O(n^2)$
    490 
    491 **Code (C++)**
    492 
    493 ```
    494 #include <iostream>
    495 #include <vector>
    496 #include <cstring>
    497 #include <assert.h>
    498 #include <set>
    499 using namespace std;
    500  
    501 #define ll long long
    502  
    503 const int INF = 998244353;
    504 // const int BOUND = 1e9;
    505  
    506 void solve() {
    507   int n; cin >> n;
    508   int BOUND; cin >> BOUND;
    509   string s; cin >> s;
    510   s = "P" + s + "S";
    511   vector<ll> b(n + 2);
    512   for (int i = 0; i < n; ++i) cin >> b[i + 1];
    513   ll ans = 0;
    514   set<ll> done;
    515   for (int i = 0; i < n + 1; ++i) {
    516     ll sum = b[i] + b[i + 1];
    517     if (done.count(sum)) continue;
    518     int dp[n + 2][2];
    519     for (int j = 0; j < n + 2; ++j) for (int k = 0; k < 2; ++k) dp[j][k] = -1;
    520     // ["P", "S"]
    521     dp[0][0] = 1;
    522     for (int j = 1; j < n + 2; ++j) {
    523       bool tr[2]; tr[0] = tr[1] = true;
    524       if (s[j] == 'P') tr[1] = false;
    525       else if (s[j] == 'S') tr[0] = false;
    526       if (abs(b[j] - b[j - 1]) <= BOUND) {
    527         for (int k = 0; k < 2; ++k)
    528           if (dp[j - 1][k] > -1 && tr[k]) dp[j][k] = dp[j - 1][k];
    529       }
    530       if (dp[j - 1][0] > -1 && tr[1] && sum == b[j] + b[j - 1]) {
    531         // "P" -> "S":
    532         if (dp[j][1] < 0) dp[j][1] = 0;
    533         dp[j][1] = (dp[j][1] + dp[j - 1][0]) % INF;
    534       }
    535       if (dp[j - 1][1] > -1 && tr[0]) {
    536         // "S" -> "P":
    537         ll add = b[j] + b[j - 1] - sum;
    538         ll large = max(abs(add / 2), abs(add - add / 2));
    539         if (large <= BOUND) {
    540           if (dp[j][0] < 0) dp[j][0] = 0;
    541           dp[j][0] = (dp[j][0] + dp[j - 1][1]) % INF;
    542         }
    543       }
    544     }
    545     if (dp[n + 1][1] < 0) continue;
    546     ans = (ans + dp[n + 1][1]) % INF;
    547     done.insert(sum);
    548   }
    549   cout << ans << '\n';
    550 }
    551  
    552 int main() {
    553   ios::sync_with_stdio(false); cin.tie(NULL);
    554   int t; cin >> t;
    555   for (int i = 0; i < t; ++i) solve();
    556   return 0;
    557 }
    558 ```
    559 
    560 #### [1984G - Magic Trick II](/contest/1984/problem/G "Codeforces Global Round 26")
    561 
    562 Problem Credits: [null_awe](/profile/null_awe "Grandmaster null_awe")   
    563 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe")
    564 
    565 **Hint 1**
    566 
    567 Solve what the maximum $k$ will be for different types of arrays.
    568 
    569 **Hint 2**
    570 
    571 The maximum is always close to $n$.
    572 
    573 **Solution**
    574 
    575 There exists two trivial cases. If array is already sorted, $k = n$. If array is cyclic shift of sorted array, $k = n - 1$. Now, $k = n - 2$ and $k = n - 3$ is sufficient to sort any array.
    576 
    577 Let's assume $n$ is odd first, and construct an answer in the general case with $k = n - 2$. Because $k$ is so large, our operations are limited in choices. If we represent the array as a cyclic array with a divider representing the end of the array, an operation can be seen as two choices:
    578 
    579 1. Move the divider $2$ positions in any direction.
    580 2. Swap the two numbers around the divider, then move the divider by $1$ position in any direction.
    581 
    582 With this representation, the construction becomes quite easy. Because $n$ is odd, we can use the first type of operation to put the divider wherever we want. Then, using the second type of operation, if our divider is on the right side of a specific number, we can move it all the way to the right by swapping, then moving the divider right by $1$ position.
    583 
    584 Because we are able to do this, we can bubble sort. For each number, position the divider in $O(n)$ moves, then move it to the very right in another $O(n)$ moves. There are $n$ numbers total, so this takes a total of around $2n^2$ operations, less if optimized.
    585 
    586 What if $n$ is even? In this case $k = n - 2$ is not always guaranteed to work. The motivation for seeing this can come from the fact that you can't place the divider anywhere just by using type $1$ operations.
    587 
    588 As a lower bound, we know that $k = n - 3$ will always work. We can use operations to move the largest number to the very end, then we basically have an array of length $n - 1$ with $k = n - 3$, which is the odd case we presented earlier.
    589 
    590 So, when can we use $k = n - 2$ in the even case? Let's consider the number of inversions in the array at any given time. If $n$ is even, then $k = n - 2$ is also even, meaning that the parity of the number of inversions will never change with operations. Thus, since a sorted array will have no inversions, we cannot use $k = n - 2$ if the initial array had an odd number of inversions.
    591 
    592 If we have an even number of inversions, we can sort in a similar manner. Except, now, if the inversion constraint prevents moving the divider to the immediate right of our current number with only type $1$ operations, we can use a few type $2$ operations to fix the position of the divider (many possible strategies for this, one possible way is shown in the implementation). Overall, this should also take around $2n^2$ operations total.
    593 
    594 **Code (C++)**
    595 
    596 ```
    597 #include <iostream>
    598 #include <vector>
    599 using namespace std;
    600  
    601 #define pii pair<int, int>
    602  
    603 bool sorted(vector<int> arr, int n) {
    604   for (int i = 1; i < n; ++i) if (arr[i] < arr[i - 1]) return false;
    605   return true;
    606 }
    607  
    608 bool cyclic(vector<int> arr, int n) {
    609   for (int i = 1; i < n; ++i) if (arr[i] % n != (arr[i - 1] + 1) % n) return false;
    610   return true;
    611 }
    612  
    613 void solve() {
    614   int n; cin >> n;
    615   vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];
    616   if (sorted(arr, n)) {
    617     cout << n << "\n0\n";
    618     return;
    619   }
    620   if (cyclic(arr, n)) {
    621     cout << n - 1 << '\n';
    622     int pos;
    623     for (pos = 0; pos < n; ++pos) if (arr[pos] == 1) break;
    624     cout << pos << '\n';
    625     for (int i = 0; i < pos; ++i) {
    626       cout << "2 1\n";
    627     }
    628     return;
    629   }
    630   vector<pii> ops;
    631   if (n % 2 == 0) {
    632     int inv = 0;
    633     for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (arr[i] > arr[j]) ++inv;
    634     if (inv & 1) {
    635       int pos;
    636       for (pos = 0; pos < n; ++pos) if (arr[pos] == n) break;
    637       if (pos < 3) {
    638         for (int i = 0; i <= pos; ++i) ops.push_back({2, 1});
    639         vector<int> tmp = arr;
    640         for (int i = 0; i < n - 2; ++i) arr[i] = tmp[(i + pos + 1) % (n - 2)];
    641       }
    642       for (pos = 0; pos < n; ++pos) if (arr[pos] == n) break;
    643       for (int i = pos; i < n - 1; ++i) ops.push_back({3, 4});
    644       vector<int> tmp = arr;
    645       for (int i = 2; i < n; ++i) arr[i] = tmp[((i + pos - 3) % (n - 2)) + 2];
    646       --n;
    647     }
    648   }
    649   cout << n - 2 << '\n';
    650   int div = 0;
    651   for (int i = n; i > 0; --i) {
    652     int pos;
    653     for (pos = 0; pos < n; ++pos) if (arr[pos] == i) break;
    654     pos += 1;
    655     if (pos == i) continue;
    656     if (div % 2 != pos % 2) {
    657       if (n & 1) {
    658         while (div < n) {
    659           ops.push_back({3, 1});
    660           div += 2;
    661         }
    662         div %= n;
    663       } else {
    664         while (div != pos - 1) {
    665           if (div < pos - 1) {
    666             ops.push_back({3, 1});
    667             div += 2;
    668           } else {
    669             ops.push_back({1, 3});
    670             div -= 2;
    671           }
    672         }
    673         if (pos > 1) {
    674           ops.push_back({2, 3});
    675           swap(arr[(div + n - 1) % n], arr[div]);
    676           div = (div + n - 1) % n;
    677           --pos;
    678         }
    679         ops.push_back({3, 1});
    680         div += 2;
    681         ops.push_back({2, 3});
    682         swap(arr[(div + n - 1) % n], arr[div]);
    683         div = (div + n - 1) % n;
    684       }
    685     }
    686     while (div != pos) {
    687       if (div < pos) {
    688         ops.push_back({3, 1});
    689         div += 2;
    690       } else {
    691         ops.push_back({1, 3});
    692         div -= 2;
    693       }
    694     }
    695     for (int j = pos; j < i; ++j) {
    696       ops.push_back({2, 1});
    697       swap(arr[div - 1], arr[div]);
    698       ++div;
    699     }
    700   }
    701   if (div % 2 == 1) {
    702     while (div < n) {
    703       ops.push_back({3, 1});
    704       div += 2;
    705     }
    706     div %= n;
    707   }
    708   while (div > 0) {
    709     ops.push_back({1, 3});
    710     div -= 2;
    711   }
    712   cout << ops.size() << '\n';
    713   for (pii p : ops) {
    714     cout << p.first << ' ' << p.second << '\n';
    715   }
    716 }
    717  
    718 int main() {
    719   ios_base::sync_with_stdio(false); cin.tie(NULL);
    720   int t; cin >> t;
    721   for (int i = 0; i < t; ++i) solve();
    722   return 0;
    723 }
    724 ```
    725 
    726 #### [1984H - Tower Capturing](/contest/1984/problem/H "Codeforces Global Round 26")
    727 
    728 Problem Credits: [flamestorm](/profile/flamestorm "Master flamestorm")   
    729 Analysis: [flamestorm](/profile/flamestorm "Master flamestorm")
    730 
    731 **Hint 1**
    732 
    733 Are there any useless points?
    734 
    735 **Hint 2**
    736 
    737 Draw all triangles that contain all points inside their circumcircle. What do you notice?
    738 
    739 **Solution**
    740 
    741 **Claim.** We can't ever pick a tower inside the convex hull.
    742 
    743 **Proof.** A circle can only contain all the points if the points on the circle are on the convex hull; otherwise, the circle will necessarily split the convex hull into two parts, one of which is outside.
    744 
    745 It follows that if our initial two towers aren't on the convex hull, the answer is $0$. Also, we can safely ignore all points in the convex hull, since we'll capture them anyway, as the convex hull is the union of all triangles whose vertices are vertices of the convex hull. From now on we'll only consider points on the convex hull.
    746 
    747 Now comes the key claim of the problem.
    748 
    749 **Claim.** Call a triangle *covering* if its circumcircle contains all the points. Draw all covering triangles. We claim that these triangles form a triangulation of the convex hull.
    750 
    751 **Proof.** Recall that a triangulation is a set of triangles with pairwise non-intersecting interiors whose union is the polygon. There are two parts to the proof:
    752 
    753 1. the triangles are pairwise non-intersecting.
    754 2. their union is the polygon.
    755 
    756 Let's prove them separately.
    757 
    758 First we'll prove point (1) directly.
    759 
    760 Consider two circles through points $ABC$ and $DEF$. Of course, the convex hull needs to lie in the intersection of the two circles. In particular, the circle through $ABC$ must contain the points $DEF$, while the circle through $DEF$ must contain the points $ABC$. It follows that the two circumcircles (say, $\Omega$ and $\Psi$ respectively) have the following property:
    761 
    762 * the points $A$, $B$, $C$ lie on an arc of $\Omega$ inside $\Psi$, and
    763 * the points $D$, $E$, $F$ lie on an arc of $\Psi$ inside $\Omega$.
    764 
    765 The claim follows. Formally, we can define $U$ and $V$ as the intersection points of $\Omega$ and $\Psi$. Then if we walk along the digon $UV$ (whose edges are arcs of $\Omega$ and $\Psi$), we will pass through $A$, $B$, $C$ along one of the arcs, and $D$, $E$, $F$ on the other. This means that there is some closed convex loop passing through the points $A$, $B$, $C$ before $D$, $E$, $F$, implying those two triangles don't intersect. The proof remains the same even if some of $A$, $B$, $C$, $D$, $E$, $F$ overlap.
    766 
    767 Now we'll move on to the proof of (2). Consider any covering triangle $ABC$. WLOG suppose $AB$ is not an edge of the convex hull. Consider the points in the halfplane of $AB$ not containing $C$, and let $C'$ be the point among these such that $\angle AC'B$ is minimized. Then it follows that $ABC'$ is also covering. It's easy to see why this works and why $C'$ is unique by the inscribed angle theorem.
    768 
    769 As a result, given any covering triangle, we can recursively triangulate the regions it cuts off by a chord. Thus, inductively, the whole polygon will be triangulated. We are done with the proof.
    770 
    771 Note that this implies our original three towers in the problem must form a covering triangle, since we create a covering triangle after every operation; thus, at the end of these operations, all but possibly one of these triangles is covering (the "possibly one" is the initial triangle). But such a covering triangulation exists and is unique, as shown, so our initial triangle in fact must be covering.
    772 
    773 Now on to the actual operations present in the problem. Using them, we can "construct" the triangulation one step at a time using operations like the one mentioned. Of course, the triangulation is unique, so the only change we can do is the order in which we construct the triangles.
    774 
    775 Consider the dual tree of the triangulation (that is, make a vertex for each triangle and an edge between those vertices corresponding to two triangles that share a diagonal of the convex hull). In an operation, we attach a leaf to any vertex, and in the end we end up with the final dual tree. Note that we can start growing the tree at either triangle adjacent to our original diagonal; that is, if our original points are $A$ and $B$, then we need to consider rooting our tree at either $T_1$ or $T_2$, where those are the two triangles that contain the edge $AB$ (note that $T_2$ may not exist).
    776 
    777 Let's reverse time. Then given the final tree (rooted at either $T_1$ or $T_2$), in an operation we prune a leaf (a leaf here is a vertex with no children). How many ways can we prune all the leaves?
    778 
    779 This is a standard dynamic programming problem, since at each step we need to prune all of our children before we prune ourselves. In particular, if the sizes of our childrens' subtrees are $s_1, \dots, s_k$, then our answer is $\binom{s_1 + \dots + s_k}{s_1, \dots, s_k} \cdot \prod_{i=1}^{k} \mathrm{ans}(\mathrm{child}_i)$. This DP runs in $\mathcal{O}(n)$ time, so it is not a problem to compute.
    780 
    781 We can easily compute the triangulation in $\mathcal{O}(n^2)$ time as follows: given an edge $PQ$, we need to find the point $R$ in a halfplane such that $(PQR)$ covers all points, and as mentioned before, by the inscribed angle theorem this is precisely the point $R$ such that $PQR'$ is minimized. So you can find it with an $\mathcal{O}(n)$ sweep and add the new edges to our triangulation.
    782 
    783 Therefore the solution runs in $\mathcal{O}(n^2)$, but the validator takes $\mathcal{O}(n^3)$ to check. We accepted slower solutions in $\mathcal{O}(n^3)$ as well, and even $\mathcal{O}(n^4)$ with a decent constant factor (which are relatively hard to cut).
    784 
    785 A note about implementation: I'm not very good at it, so my code below is a bit messy. Also, to keep the computations in integers, I needed to use big integers at exactly one point, but it's not so bad: you only need to implement big integer multiplication and comparison, which I shamelessly stole from [jeroenodb](/profile/jeroenodb "International Grandmaster jeroenodb"). You may not need to use it, and can pass using floating-point numbers.
    786 
    787 **Code (C++)**
    788 
    789 ```
    790 #include <bits/stdc++.h>
    791 
    792 using namespace std;
    793 
    794 const int MAX = 200007;
    795 const int MOD = 998244353;
    796 
    797 struct bignum {
    798     static constexpr long long B = 1LL<<30;
    799     static constexpr int N = 6;
    800     array<long long, N> b = {};
    801     bignum() {}
    802     bignum(long long a) {
    803         b[2] = (a / B) / B;
    804         b[1] = (a / B) % B;
    805         b[0] = a % B;
    806     }
    807     bignum operator*(const bignum& o) {
    808         bignum res;
    809         for (int i = 0; i < N; i++) {
    810 		    for (int j = 0; j + i < N; j++) {
    811 		        res.b[i + j] += b[i] * o.b[j];
    812 		        for (int k = i + j; k + 1 < N; k++) {
    813 		            auto tmp = res.b[k] / B;
    814 		            res.b[k + 1] += tmp;
    815 		            res.b[k] -= tmp * B;
    816 		        }
    817 		    }
    818 		}
    819         return res;
    820     }
    821     bool operator<=(const bignum& o) const {
    822         if (b == o.b) return true;
    823         return lexicographical_compare(b.rbegin(),b.rend(),o.b.rbegin(),o.b.rend());
    824     }
    825 };
    826 
    827 template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
    828 template<class T>
    829 struct Point {
    830 	typedef Point P;
    831 	T x, y;
    832 	explicit Point(T x=0, T y=0) : x(x), y(y) {}
    833 	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
    834 	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
    835 	P operator+(P p) const { return P(x+p.x, y+p.y); }
    836 	P operator-(P p) const { return P(x-p.x, y-p.y); }
    837 	P operator*(T d) const { return P(x*d, y*d); }
    838 	P operator/(T d) const { return P(x/d, y/d); }
    839 	T dot(P p) const { return x*p.x + y*p.y; }
    840 	T cross(P p) const { return x*p.y - y*p.x; }
    841 	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
    842 	T dist2() const { return x*x + y*y; }
    843 	double dist() const { return sqrt((double)dist2()); }
    844 	// angle to x-axis in interval [-pi, pi]
    845 	double angle() const { return atan2(y, x); }
    846 	P unit() const { return *this/dist(); } // makes dist()=1
    847 	P perp() const { return P(-y, x); } // rotates +90 degrees
    848 	P normal() const { return perp().unit(); }
    849 	// returns point rotated 'a' radians ccw around the origin
    850 	P rotate(double a) const {
    851 		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
    852 	friend ostream& operator<<(ostream& os, P p) {
    853 		return os << "(" << p.x << "," << p.y << ")"; }
    854 	friend istream& operator>>(istream& is, P& p) {
    855 		return is >> p.x >> p.y; }
    856 };
    857 
    858 typedef Point<long long> P;
    859 vector<P> convexHull(vector<P> pts) {
    860 	if (pts.size() <= 1) return pts;
    861 	sort(pts.begin(), pts.end());
    862 	vector<P> h(pts.size()+1);
    863 	int s = 0, t = 0;
    864 	for (int it = 2; it--; s = --t, reverse(pts.begin(), pts.end()))
    865 		for (P p : pts) {
    866 			while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
    867 			h[t++] = p;
    868 		}
    869 	return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
    870 }
    871 
    872 int n, t;
    873 long long inv[MAX], fact[MAX], invfact[MAX];
    874 vector<P> v;
    875 
    876 void orient(P &a, P &b, P &c) {
    877 	// move points a, b, c to be in counterclockwise order
    878 	long long val = (b - a).cross(c - a);
    879 	assert(val != 0);
    880 	if (val < 0) {swap(a, c);} 
    881 }
    882 
    883 pair<long long, long long> angleComp(P a, P b, P c) {
    884 	// get a (scaled) value of f(cos(angle ABC))
    885 	P ab = a - b, cb = c - b;
    886 	long long dt = ab.dot(cb);
    887 	dt *= dt;
    888 	int sgn = (ab.dist2() + cb.dist2() >= (a - c).dist2() ? 1 : -1);
    889 	return make_pair(sgn * dt, ab.dist2() * cb.dist2());
    890 }
    891 
    892 bool inCircle(P a, P b, P c, P d) {
    893 	// is D in (or on) (ABC)?
    894 	orient(a, b, c);
    895 	P ad = a - d, bd = b - d, cd = c - d;
    896 	return (
    897 		ad.dist2() * (bd.x * cd.y - bd.y * cd.x) -
    898 		bd.dist2() * (ad.x * cd.y - ad.y * cd.x) +
    899 		cd.dist2() * (ad.x * bd.y - ad.y * bd.x)
    900 	) >= 0;
    901 }
    902 
    903 pair<bool, int> check(int l, int r) {
    904 	int start = l, finish = r;
    905 	if (finish < start) {finish += n;}
    906 	pair<long long, long long> best = make_pair(-MOD, 1);
    907 	int w = -1;
    908 	for (int i = start + 1; i < finish; i++) {
    909 		pair<long long, long long> val = angleComp(v[l], v[i % n], v[r]);
    910 		bignum v1 = bignum(val.first) * bignum(best.second);
    911 		bignum v2 = bignum(val.second) * bignum(best.first);
    912 		if (!(v1 <= v2)) {
    913 			best = val;
    914 			w = i % n;
    915 		}
    916 	}
    917 	if (w == -1) {
    918 		// cout << v[l] << ' ' << v[r] << " empty?\n";
    919 		return make_pair(true, -1);
    920 	}
    921 	// cout << v[l] << ' ' << v[r] << " connects to " << v[w] << "?\n";
    922 	for (P Q : v) {
    923 		if (!inCircle(v[l], v[w], v[r], Q)) {return make_pair(false, -1);}
    924 	}
    925 	return make_pair(true, w);
    926 }
    927 
    928 void reset(int n) {
    929 	v.clear();
    930 	// for (int i = 0; i < n + 5; i++) {
    931 		// g[i].clear();
    932 		// child[i].clear();
    933 	// }
    934 	t = 1;
    935 }
    936 
    937 void solve() {
    938 	cin >> n;
    939 	reset(n);
    940 	vector<P> pts(n);
    941 	for (int i = 0; i < n; i++) {
    942 		cin >> pts[i];
    943 	}
    944 	vector<P> us{pts[0], pts[1]};
    945 	vector<int> us_vals;
    946 	v = convexHull(pts);
    947 	n = v.size();
    948 	for (auto P : us) {
    949 		int i = 0; bool hit = false;
    950 		for (auto Q : v) {
    951 			if (P == Q) {us_vals.push_back(i); hit = true;}
    952 			i++;
    953 		}
    954 		if (!hit) {cout << 0 << '\n'; return;}
    955 	}
    956 	if (v.size() <= 3) {cout << 1 << '\n'; return;}
    957 	queue<pair<pair<int, int>, int>> q;
    958 	vector<int> child[MAX];
    959 	q.push(make_pair(make_pair(us_vals[0], us_vals[1]), -1));
    960 	q.push(make_pair(make_pair(us_vals[1], us_vals[0]), -1));
    961 	while (!q.empty()) {
    962 		auto p = q.front();
    963 		q.pop();
    964 		pair<bool, int> resp = check(p.first.first, p.first.second);
    965 		if (!resp.first) {cout << 0 << '\n'; return;}
    966 		if (resp.second == -1) {continue;}
    967 		q.push(make_pair(make_pair(p.first.first, resp.second), t));
    968 		q.push(make_pair(make_pair(resp.second, p.first.second), t));
    969 		if (p.second != -1) {
    970 			child[p.second].push_back(t);
    971 		}
    972 		t++;
    973 	}
    974 	// for (int i = 1; i <= n - 2; i++) {
    975 		// cout << i << ": ";
    976 		// for (int j : child[i]) {cout << j << ' ';}
    977 		// cout << '\n';
    978 	// }
    979 	bool edge_case = true; // both 1 and 2 are roots
    980 	for (int j : child[1]) {
    981 		if (j == 2) {edge_case = false;} // only 1 is root
    982 	}
    983 	
    984 	vector<long long> dp(n + 7);
    985 	vector<int> sz(n + 7);
    986 	
    987 	auto cnt = [&](auto self, int v) -> int {
    988 		if (sz[v] != -1) {return sz[v];}
    989 		int res = 1;
    990 		if (!child[v].empty()) {
    991 			for (int u : child[v]) {
    992 				res += self(self, u);
    993 			}
    994 		}
    995 		sz[v] = res;
    996 		return res;
    997 	};
    998 	
    999 	auto f = [&](auto self, int v) -> long long {
   1000 		if (dp[v] != -1LL) {return dp[v];}
   1001 		long long res = 1LL;
   1002 		if (!child[v].empty()) {
   1003 			res = (res * fact[cnt(cnt, v) - 1]) % MOD;
   1004 			for (int u : child[v]) {
   1005 				res = (res * self(self, u)) % MOD;
   1006 				res = (res * invfact[cnt(cnt, u)]) % MOD;
   1007 			}
   1008 		}
   1009 		dp[v] = res;
   1010 		return res;
   1011 	};
   1012 
   1013 	if (edge_case) {child[1].push_back(2);}
   1014 	
   1015 	fill(dp.begin(), dp.end(), -1LL);
   1016 	fill(sz.begin(), sz.end(), -1);
   1017 	long long res = f(f, 1);
   1018 	
   1019 	if (edge_case) {
   1020 		child[1].erase(remove(child[1].begin(), child[1].end(), 2), child[1].end());
   1021 		child[2].push_back(1);
   1022 		fill(dp.begin(), dp.end(), -1LL);
   1023 		fill(sz.begin(), sz.end(), -1);
   1024 		res = (res + f(f, 2)) % MOD;
   1025 	}
   1026 	
   1027 	cout << res << '\n';
   1028 }
   1029 
   1030 int main() {
   1031 	ios::sync_with_stdio(false);
   1032 	cin.tie(nullptr);
   1033 	inv[0] = inv[1] = 1;
   1034 	for (int i = 2; i < MAX; i++) {
   1035 		inv[i] = MOD - (long long)(MOD / i) * inv[MOD % i] % MOD;
   1036 	}
   1037 	fact[0] = fact[1] = 1; invfact[0] = invfact[1] = 1;
   1038 	for (int i = 2; i < MAX; i++) {
   1039 		fact[i] = (fact[i - 1] * (long long)i) % MOD;
   1040 		invfact[i] = (invfact[i - 1] * inv[i]) % MOD;
   1041 	}
   1042 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
   1043 	// solve();
   1044 }
   1045 ```