codeforces-scrape

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

2226.md (32930B)


      1 Source: https://codeforces.com/blog/entry/153150
      2 
      3 Thanks for participating. We hope you liked the problems and enjoyed the round.
      4 
      5 #### [2226A - Disturbing Distribution](/contest/2226/problem/A "Codeforces Round 1095 (Div. 2)")
      6 
      7 Idea: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
      8  Preparation: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
      9  Solution: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")
     10 
     11 **Solution**
     12 
     13 For any two positive integers $x$ and $y$, observe that $x \times y \ge x + y$ when $x \gt 1$ and $y \gt 1$. Thus, it is never optimal to choose two elements that are more than $1$ in a single operation. Also, it is optimal to choose as many $1$'s as possible in a single operation.
     14 
     15 Hence, we opt to choose subsequences of the form $[1, 1, \ldots, x]$ and delete them. Note that the cost for this operation is equal to $x$. Therefore, the answer is just the sum of elements that are more than $1$. But if the last element is $1$, it cannot be clubbed with any "more than $1$ element", and it adds $1$ to the answer.
     16 
     17 Time Complexity: $\mathcal{O(n)}$
     18 
     19 **Implementation**
     20 
     21 ```
     22 #include<bits/stdc++.h>
     23 using namespace std;
     24  
     25 int main(){
     26  
     27     int t;
     28     cin >> t;
     29  
     30     while(t--){
     31         
     32         int n;
     33         cin >> n;
     34  
     35         vector<int> a(n);
     36         for(int i = 0; i < n; i++) cin >> a[i];
     37  
     38         int ans = 0;
     39  
     40         for(int i = 0; i < n; i++) if(a[i] > 1) ans += a[i];
     41         if(a.back() == 1) ans++;
     42  
     43         cout << ans << '\n';
     44  
     45     }
     46 }
     47 ```
     48 
     49 **Rate The Problem!**
     50 
     51 * Best Problem
     52 * Good Problem
     53 * Okay Problem
     54 * Bad Problem
     55 * Didn't Solve
     56 
     57 #### [2226B - Everything Everywhere](/contest/2226/problem/B "Codeforces Round 1095 (Div. 2)")
     58 
     59 Idea: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
     60  Preparation: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
     61  Solution: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")
     62 
     63 **Solution**
     64 
     65 For any array $a$, let $\text{g}$ denote the $\text{gcd}$ of all the elements in the array $a$. Note that every element in $a$ is a multiple of $\text{g}$. Let the maximum element be equal to $M \cdot \text{g}$ and the minimum element be equal to $m \cdot \text{g}$.
     66 
     67 If array $a$ is good, the given condition simplifies to $M - m = 1$. This implies that $a$ must contain exactly two distinct elements, and they should be of the form $m \cdot \text{g}$ and $(m+1) \cdot \text{g}$.
     68 
     69 Note that you are given a permutation rather than any array. Since all the elements in a permutation are distinct, any subarray that has length not equal to $2$ is guaranteed to be not good. Thus, we only need to check those subarrays that have a length equal to $2$.
     70 
     71 This is trivial. For every $i$, check whether the array $[p_i, p_{i+1}]$ satisfies the given condition.
     72 
     73 Time Complexity: $\mathcal{O(n)}$
     74 
     75 **Implementation**
     76 
     77 ```
     78 #include<bits/stdc++.h>
     79 using namespace std;
     80  
     81 int main(){
     82  
     83     int t;
     84     cin >> t;
     85  
     86     while(t--){
     87         int n;
     88         cin >> n;
     89  
     90         vector<int> a(n);
     91         for(int i = 0; i < n; i++) cin >> a[i];
     92  
     93         int ans = 0;
     94         for(int i = 0; i < n - 1; i++) if(a[i] % (a[i] - a[i + 1]) == 0) ans++;
     95         
     96         cout << ans << '\n';
     97     }
     98  
     99     return 0;
    100 }
    101 ```
    102 
    103 **Rate The Problem!**
    104 
    105 * Best Problem
    106 * Good Problem
    107 * Okay Problem
    108 * Bad Problem
    109 * Didn't Solve
    110 
    111 #### [2226C - Mental Monumental (Easy Version)](/contest/2226/problem/C "Codeforces Round 1095 (Div. 2)")
    112 
    113 Idea: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    114  Preparation: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    115  Solution: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")
    116 
    117 **Solution**
    118 
    119 For a fixed value of $x$ and varying $y$, let us analyze what values $x \, \bmod \, y$ can attain.
    120 
    121 To start with, if $y \gt x$, $x \, \bmod \, y = x$. Otherwise, if $y \le x$, $x \, \bmod \, y$ will always be less than $\frac{x}{2}$. We can prove this by breaking down the condition $y \le x$ into two cases:
    122 
    123 * $y \le \frac{x}{2}$: Since the remainder must be less than the divisor, we have $x \, \bmod \, y \lt y \le \frac{x}{2}$. Thus, $x \, \bmod \, y \lt \frac{x}{2}$.
    124 * $\frac{x}{2} \lt y \le x$: In this case, note that $x \, \bmod \, y = x - y \lt x - \frac{x}{2} = \frac{x}{2}$. Thus, $x \, \bmod \, y \lt \frac{x}{2}$.
    125 
    126 And finally, we note that $x \, \bmod \, y$ can be equal to $x$ (choose any $y$ greater than $x$) or it can attain any value $z \lt \frac{x}{2}$ (choose $y = x - z$).
    127 
    128 Now, let us try to solve the given problem. Let us call an integer $k$ good if we can attain all the values $0, 1, 2, \ldots, k-1$ in the array $a$ after performing the operation. Note that the answer for this problem is the maximum integer $k$, which is good. Furthermore, observe that if a particular value $k$ is good, then $k-1$ is also guaranteed to be good. This monotonic behavior naturally leads to the use of **binary search** to determine the maximum such $k$.
    129 
    130 The only thing left now is "given an integer value $k$, how do we check if it is good?" To check if $k$ is good, we need to check whether we can attain all the values $0, 1, 2, \ldots, k-1$ in the array by performing an operation. To attain a value $x$ ($0 \le x \lt k$), we need atleast one index $i$ that satisfies $a_i = x$ or $a_i \gt 2x$ (since $a_i \, \bmod \, b_i$ can be either $a_i$ or $ \lt \frac{a_i}{2}$). We must also make sure that every value is assigned to at most one position.
    131 
    132 To handle this, let us process the required values in decreasing order, i.e., from $k-1$ to $0$. We maintain a multiset of all unused array elements. For a current value $x$, we do the following:
    133 
    134 * If $x$ itself is present in the multiset, then we remove one occurrence of $x$.
    135 * Otherwise, we need some unused value $a_i$ such that $a_i \gt 2x$. Among all such values, we can choose one.
    136 
    137 If at some step neither of the above is possible, then the current value $x$ cannot be formed, and hence $k$ is not good.
    138 
    139 The above strategy works because any value greater than $2x$ can always be reduced to $x$, and when both $x$ and some value $ \gt 2x$ are available, it is optimal to choose the smallest feasible value, since larger elements are more flexible and may still be needed to construct smaller values later.
    140 
    141 Time Complexity: $\mathcal{O}(n \cdot \log^2 n)$
    142 
    143 **Implementation**
    144 
    145 ```
    146 #include<bits/stdc++.h>
    147 using namespace std;
    148 #define ll long long
    149  
    150 int main(){
    151  
    152     int t;
    153     cin >> t;
    154  
    155     while(t--){
    156         int n;
    157         cin >> n;
    158  
    159         vector<int> a(n);
    160         for(int i = 0; i < n; i++) cin >> a[i];
    161  
    162         multiset<int> ms(a.begin(), a.end());
    163  
    164         int l = 0, r = n + 1;
    165         while(l < r){
    166             int md = (l + r) / 2;
    167  
    168             assert((int)ms.size() == n);
    169             
    170             bool is = 1;
    171             vector<int> removed;
    172  
    173             for(int i = md - 1; i >= 0; i--){
    174                 if(ms.count(i)){
    175                     removed.push_back(i);
    176                     ms.erase(ms.find(i));
    177                     continue;
    178                 }
    179                 else{
    180                     int x = *ms.rbegin();
    181                     if(x < 2*i + 1){
    182                         is = 0;
    183                         break;
    184                     }
    185                     removed.push_back(x);
    186                     ms.erase(ms.find(x));
    187                 }
    188             }
    189  
    190             for(auto& z : removed) ms.insert(z);
    191  
    192             if(is) l = md + 1;
    193             else r = md;
    194         }
    195  
    196         assert(l > 0);
    197         --l;
    198  
    199         cout << l << '\n';
    200     }
    201     
    202 }
    203 ```
    204 
    205 **Rate The Problem!**
    206 
    207 * Best Problem
    208 * Good Problem
    209 * Okay Problem
    210 * Bad Problem
    211 * Didn't Solve
    212 
    213 #### [2226D - Reserved Reversals](/contest/2226/problem/D "Codeforces Round 1095 (Div. 2)")
    214 
    215 Idea: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    216  Preparation: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    217  Solution: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")
    218 
    219 **Solution**
    220 
    221 Let us consider odd and even values separately. If odd values can be sorted within themselves, and even values can be sorted within themselves, then it is easy to see that the whole array can be sorted eventually (we can just apply adjacent reversals by choosing segments of length $2$ of which one is even and one is odd).
    222 
    223 Now, let us consider even values separately. Let the subsequence of even values be $[e_1, e_2, \ldots, e_m]$. For each $i$ from $1$ to $m$, we aim to make the prefix up to index $i$ sorted. That is, we try to place $e_i$ in its correct position in the sorted order, assuming that the prefix up to index $i-1$ is already sorted.
    224 
    225 Let the sorted prefix up to index $i-1$ be $[E_1, E_2, \ldots, E_{i-1}]$, where $E_1 \le E_2 \le \cdots \le E_{i-1}$. If $e_i \ge E_{i-1}$, we can directly extend the prefix and proceed to index $i+1$. Otherwise, if $e_i \lt E_{i-1}$, we must change the relative order of $e_i$ and $E_{i-1}$. So, we must apply an operation involving both of them (otherwise, the relative order will not change). In order to apply such an operation, we must at least need an odd integer $z$ such that either $z \gt E_{i-1}$ or $z \lt e_i$. If we cannot find such $z$, we can instantly conclude that the array $a$ cannot be sorted.
    226 
    227 If we can find such $z$, it is sufficient, and we can use it to change the relative order of $e_i$ and $E_{i-1}$ without changing the relative order of any other pair of elements having the same parity in the array $a$. Proof is as follows:
    228 
    229 Let the values $e_i$, $E_{i-1}$, $z$ appear in the array $a$ in the following manner: $[\ldots, E_{i-1}, \ldots, e_i, \ldots, z, \ldots]$. Note that there won't be any even value in between $E_{i-1}$ and $e_i$. So, let's move all the odd values between them to the left of $E_{i-1}$ by making adjacent reversals. There can be both even and odd values between $e_i$ and $z$; we propagate all the even values to the right of $z$ and all the odd values to the left of $E_{i-1}$ by making adjacent reversals. Now, the array $a$ looks like: $[\ldots, E_{i-1}, e_i, z, \ldots]$. Finally, choose the segment with all three elements and reverse it, we get the desired order: $[\ldots, z, e_i, E_{i-1}, \ldots]$.
    230 
    231 We follow the same idea with $E_{i-2}, E_{i-3} \ldots$. Finally, we place $e_i$ in its correct position in the sorted order. So, we check the existence of such $z$ for every inversion (can be easily done by storing the prefix maximum).
    232 
    233 We follow the same process with odd values. To conclude, if we find any inversion within a parity and cannot find a valid $z$ of opposite parity, the answer is NO. Otherwise, the answer is YES.
    234 
    235 Time Complexity: $\mathcal{O(n)}$.
    236 
    237 **Implementation**
    238 
    239 ```
    240 #include<bits/stdc++.h>
    241 using namespace std;
    242 #define ll long long
    243  
    244 int main(){
    245  
    246     int t;
    247     cin >> t;
    248  
    249     while(t--){
    250         
    251         int n;
    252         cin >> n;
    253  
    254         vector<int> a(n);
    255         for(int i = 0; i < n; i++) cin >> a[i];
    256  
    257         vector<int> even, odd;
    258         for(auto& z : a){
    259             if(z % 2) odd.push_back(z);
    260             else even.push_back(z);
    261         }
    262  
    263         int even_min = 1e9;
    264         int even_max = -1e9;
    265         int odd_min = 1e9;
    266         int odd_max = -1e9;
    267  
    268         if(!even.empty()){
    269             for(auto& z : even){
    270                 even_min = min(even_min, z);
    271                 even_max = max(even_max, z);
    272             }
    273         }
    274  
    275         if(!odd.empty()){
    276             for(auto& z : odd){
    277                 odd_min = min(odd_min, z);
    278                 odd_max = max(odd_max, z);
    279             }
    280         }
    281  
    282         bool is = 1;
    283  
    284         if(even.size() > 1){
    285  
    286             int mx = even[0];
    287  
    288             for(int i = 1; i < even.size(); i++){
    289                 if(mx > even[i]){
    290                     if(odd_min > even[i] && odd_max < mx){
    291                         is = 0;
    292                         break;
    293                     }
    294                 }
    295                 else{
    296                     mx = even[i];
    297                 }
    298             }
    299         }
    300  
    301         if(odd.size() > 1){
    302             
    303             int mx = odd[0];
    304  
    305             for(int i = 1; i < odd.size(); i++){
    306                 if(mx > odd[i]){
    307                     if(even_min > odd[i] && even_max < mx){
    308                         is = 0;
    309                         break;
    310                     }
    311                 }
    312                 else{
    313                     mx = odd[i];
    314                 }
    315             }
    316         }
    317  
    318         if(is) cout << "YES\n";
    319         else cout << "NO\n";
    320  
    321     }
    322 }
    323 ```
    324 
    325 **Rate The Problem!**
    326 
    327 * Best Problem
    328 * Good Problem
    329 * Okay Problem
    330 * Bad Problem
    331 * Didn't Solve
    332 
    333 #### [2226E - Mental Monumental (Hard Version)](/contest/2226/problem/E "Codeforces Round 1095 (Div. 2)")
    334 
    335 Huge thanks to [chromate00](/profile/chromate00 "Expert chromate00") for suggesting this task.   
    336  Preparation: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    337  Solution: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    338 
    339 **Solution**
    340 
    341 First, read the tutorial for the easy version of the problem.
    342 
    343 Let's call a number $m$ *fixed* if for some $i$, we have $a_i=m$, and we choose $b_i \gt m$ (so that $a_i \operatorname{mod} b_i = a_i$). Recall that from the easy version, when we want to determine whether an answer $k$ is possible to achieve, we should greedily fix as many numbers under $k$ as possible, and then check if assigning the other numbers so that $a_i \gt 2(a_i \operatorname{mod} b_i)$ is possible.
    344 
    345 Our first useful observation for the hard version is that the answer is monotonic in terms of prefix. That is, the answer for the prefix of size $i$ must be at least the answer for the prefix of size $i-1$. This motivates us to use two pointers on the prefix and the answer. That is, for each prefix, increment our answer as much as possible.
    346 
    347 Unfortunately, both updating to a new prefix and incrementing the answer by $1$ is hard. For example, suppose our current answer is $3$, and we are trying to increment it to $4$. It is possible that for some $a_i=4$, we have $b_i=3$ (so we get $a_i \operatorname{mod} b_i=1$). When we incremented our answer to $4$, it is optimal to reassign the $b_i=5$ so that $4$ is fixed. This creates a chain of updates of assignments, and maintaining all updates directly is too slow.
    348 
    349 Therefore, we need a way to check whether an assignment is possible efficiently. Call the multiset of values in $a$ that is not used to fix "offerers", and call the set of values of $a_i \operatorname{mod} b_i$ we need "receivers". Our job is to match each receiver to an offerer that is more than twice its value. Suppose we already fixed our set of receivers and offerers — how do we check whether a matching is possible? This is a classic result: we should loop through receivers from smallest to largest and match it to the smallest offerer remaining that it can match to.
    350 
    351 Let's look at it a different way. Consider each prefix of receivers from largest to smallest. In order for it to be possible to match to only the largest receiver (call it $x$), we need an offerer of at least $2x+1$. What about it to be possible to match the largest two receivers? (call it $x,y$ for $x \gt y$). Then, we need at least two numbers of at least $2y+1$, *and* for the requirement for $x$ to be satisfied. Continuing this on, for a prefix of $p$ receivers with the smallest one being $q$, we need at least $p$ offerers of at least $2q+1$, *and* for the requirements of all prefixes before it to be satisfied.
    352 
    353 Now, let's bring this set of requirements to a data structure. A segment tree is an appropriate choice. Define the segment tree such that the value at index $i$ is (number of offerers at least $2i+1$ — number of receivers at least $i$). To check whether the current answer is possible, we can query the minimum in the segment tree, and if it is nonnegative, then it is possible. Incrementing the prefix and answer can both be described as range additions. Thus, the problem is solved in $O(n\log n)$ time.
    354 
    355 Time Complexity: $\mathcal{O(n \log n)}$
    356 
    357 **Implementation**
    358 
    359 ```
    360 #include <bits/stdc++.h>
    361 #define int long long
    362 #define ll long long
    363 #define pii pair<int,int>
    364 #define fi first
    365 #define se second 
    366 using namespace std;
    367  
    368 struct segtree {
    369     const static int INF = 1e18; 
    370     int l, r, v = 0, lz = 0; 
    371     segtree *lc, *rc; 
    372     segtree* getmem(); 
    373     segtree() : segtree(-1, -1) {}; 
    374     segtree(int l, int r) : l(l), r(r) {
    375         if (l==r) return; 
    376         int m=(l+r)/2; 
    377         lc=getmem(); *lc=segtree(l,m); 
    378         rc=getmem(); *rc=segtree(m+1,r); 
    379     }
    380     int getv() {
    381         return v+lz; 
    382     }
    383     int op(int a, int b) {
    384         return min(a,b); 
    385     }
    386     void upd(int i, int x) {
    387         add(i,i,x-q(i,i)); 
    388     }
    389     void add(int ql, int qr, int x) {
    390         if (r<ql||qr<l) return; 
    391         if (ql<=l&&r<=qr) {lz+=x; return;}
    392         lc->add(ql,qr,x); rc->add(ql,qr,x); 
    393         v=op(lc->getv(), rc->getv()); 
    394     }
    395     int q(int ql, int qr) {
    396         if (qr<l||r<ql) return INF; 
    397         if (ql<=l&&r<=qr) return getv(); 
    398         return op(lc->q(ql,qr), rc->q(ql,qr))+lz; 
    399     }
    400 };
    401 segtree mem[1000000]; int memsz=0; 
    402 segtree* segtree::getmem() {
    403     return &mem[memsz++]; 
    404 }
    405  
    406 void solve() {
    407     int n; cin >> n;
    408     vector<int> v(n);
    409     unordered_map<int,int> m; 
    410     segtree st(0,n+2); 
    411     int i = 0; 
    412     st.upd(0,-1); 
    413     for (int &r:v) {
    414         cin >> r; 
    415         if (m[r]||r>i) {
    416             st.add(0,(r-1)/2,1); 
    417         } 
    418         else {
    419             st.upd(r,1e9); 
    420             st.add(0,r,1); 
    421         }
    422         m[r]++; 
    423         while (1) {
    424         // for (int j = 0; j < n; j++) cout << st.q(j,j) << " "; cout << "\n"; 
    425             if (st.q(0,i)<0) break; 
    426             i++; 
    427             st.add(0,i,-1); 
    428             if (m[i]) {
    429                 st.upd(i,1e9); 
    430                 st.add(0,(i-1)/2,-1); 
    431                 st.add(0,i,1); 
    432             }
    433         }
    434         cout << i << " "; //cout << '\n'; 
    435     }
    436     cout << "\n"; 
    437 }
    438  
    439 int32_t main() {
    440     ios::sync_with_stdio(0); cin.tie(0);
    441     int t=1; cin >> t;
    442     while (t--) solve(); 
    443 }
    444 ```
    445 
    446 **Rate The Problem!**
    447 
    448 * Best Problem
    449 * Good Problem
    450 * Okay Problem
    451 * Bad Problem
    452 * Didn't Solve
    453 
    454 #### [2226F - Inversion Invasion](/contest/2226/problem/F "Codeforces Round 1095 (Div. 2)")
    455 
    456 Idea: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm")   
    457  Preparation: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm"), [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    458  Solution: [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")
    459 
    460 **Solution**
    461 
    462 The key observation lies in the symmetry
    463 
    464 $ \gcd(x,n)=\gcd(n-x,n) \qquad (1 \le x \lt n) $
    465 
    466 So for every value below $n$, replacing $x$ by $n-x$ keeps the $\gcd$ condition unchanged.
    467 
    468 ---
    469 
    470 Now, let us focus on the values $1,2,\ldots,n-1$. If we take any valid arrangement of these values and replace every $x$ by $n-x$, then the arrangement is still valid. Also, for any pair of values $x, y \lt n$,
    471 
    472 $ x \gt y \iff n-x \lt n-y $
    473 
    474 So every inversion becomes a non-inversion, and every non-inversion becomes an inversion. There are exactly $\binom{n-1}{2}$ pairs among the values $1,2,\ldots,n-1$. Therefore, in each complementary pair of valid permutations, the total number of inversions coming from these values is exactly $\binom{n-1}{2}$. Hence, the average contribution is
    475 
    476 $ \frac{1}{2}\binom{n-1}{2} $
    477 
    478 This is the core trick.
    479 
    480 ---
    481 
    482 Now, let us try to count the number of valid permutations of $1, 2, \ldots, n - 1$. For a divisor $d \mid n$, let $\text{cnt}_d$ denote the number of integers $v \in [1,n]$ with $\gcd(v,n)=d$. So if currently $\text{cur}_d$ positions require $\gcd$ value $d$, then the number of ways to assign values to those positions is
    483 
    484 $ P\!\left(\text{cnt}_d, \text{cur}_d\right) $
    485 
    486 Multiplying over all $d \lt n$ gives the number of ways to satisfy all nonzero constraints. Let this product be $B$. If for some $d$, we have $\text{cur}_d \gt \text{cnt}_d$, then there are no valid permutations.
    487 
    488 ---
    489 
    490 Finally, we have to add the inversions contributed by $n$. If $n$ is placed at position $i$, then it contributes exactly $n-i$ inversions, since it is larger than every value to its right and smaller than none to its left.
    491 
    492 So the whole answer is:
    493 
    494 * the symmetric contribution of values $1,2,\ldots,n-1$,
    495 * plus the position-based contribution of $n$.
    496 
    497 ---
    498 
    499 The final formulas will be as follows.
    500 
    501 Let $Z$ be the number of positions with $a_i=0$. Also define
    502 
    503 $ S=\sum_{i:\,a_i=0}(n-i) $
    504 
    505 We will have two cases depending on whether $n$ is fixed or not.
    506 
    507 **Case 1: one position is fixed to $n$**
    508 
    509 Suppose the position of $n$ is forced to be $pos_n$. Then the number of valid permutations is
    510 
    511 $Z! \cdot B$
    512 
    513 The total inversion sum is
    514 
    515 $ Z! \cdot B \cdot \left(\frac{1}{2}\binom{n-1}{2} + (n-pos_n)\right) $
    516 
    517 **Case 2: no position is fixed to $n$**
    518 
    519 Then $n$ can be placed in any zero position. For a fixed position of $n$, the remaining values can be arranged in
    520 
    521 $(Z-1)! \cdot B$
    522 
    523 ways.
    524 
    525 So the total inversion sum is
    526 
    527 $ (Z-1)! \cdot B \cdot \left(Z\cdot \frac{1}{2}\binom{n-1}{2} + S\right) $ 
    528 
    529 ---
    530 
    531 Time Complexity: $\mathcal{O(n + n \log n + q)}$.
    532 
    533 **Implementation**
    534 
    535 ```
    536 #include<bits/stdc++.h>
    537 using namespace std;
    538  
    539 #define ll long long
    540 const ll mod = 998'244'353;
    541  
    542 ll power(ll x, ll y, ll z = LLONG_MAX){
    543     ll res = 1;
    544     while(y > 0){
    545         if(y % 2) res = (res * x) % z;
    546         y /= 2;
    547         if(y) x = (x * x) % z;
    548     }
    549     return res % z;
    550 }
    551  
    552 #define MX 2'000'007
    553 ll fac[MX + 1], numInv[MX + 1], facNumInv[MX + 1];
    554  
    555 void compfac(ll z){
    556     facNumInv[0] = facNumInv[1] = numInv[0] = numInv[1] = fac[0] = 1;
    557     for(ll i = 2; i <= MX; i++) numInv[i] = numInv[z % i] * (z - z / i) % z;
    558     for(ll i = 2; i <= MX; i++) facNumInv[i] = (facNumInv[i - 1] * numInv[i]) % z;
    559     for(ll i = 1; i <= MX; i++) fac[i] = (fac[i - 1] * i) % z;
    560     return;
    561 }
    562  
    563 ll nPrmod(ll n, ll r, ll z){
    564     if(r > n) return 0;
    565     return (fac[n] * facNumInv[n - r]) % z;
    566 }
    567  
    568 int main(){
    569  
    570     ios_base::sync_with_stdio(false); cin.tie(NULL);
    571  
    572     int t;
    573     cin >> t;
    574     compfac(mod);
    575  
    576     while(t--){
    577         ll n, q;
    578         cin >> n >> q;
    579  
    580         ll val = (n - 2) * (n - 1);
    581         val /= 2;
    582         val %= mod;
    583  
    584         val *= power(2, mod - 2, mod);
    585         val %= mod;
    586  
    587         vector<ll> cnt(n + 1, 0);
    588         for(ll i = 1; i <= n; i++) cnt[gcd(i, n)]++;
    589         cnt[0] = n;
    590  
    591         vector<ll> a(n, 0);
    592         vector<ll> cur(n + 1, 0);
    593         cur[0] = n - 1;
    594  
    595         ll zerocnt = 0;
    596         ll prod = 1;
    597  
    598         ll sum = n * (n - 1);
    599         sum /= 2;
    600         sum %= mod;
    601  
    602         while(q--){
    603             ll i, x;
    604             cin >> i >> x;
    605             --i;
    606             assert(n % x == 0);
    607             assert(a[i] == 0);
    608  
    609             cur[a[i]]--;
    610  
    611             a[i] = x;
    612             if(x == n) sum = n - 1 - i, cur[0]++;
    613             else if(cur[n] == 0) sum -= (n - i - 1);
    614  
    615             if(cur[0] < 0) zerocnt = 1;
    616  
    617             ll prev = nPrmod(cnt[a[i]], cur[a[i]], mod);
    618             prod *= power(prev, mod - 2, mod);
    619             prod %= mod;
    620  
    621             cur[a[i]]++;
    622  
    623             ll after = nPrmod(cnt[a[i]], cur[a[i]], mod);
    624             prod *= after;
    625             prod %= mod;
    626  
    627             if(cur[a[i]] > cnt[a[i]]) zerocnt = 1;
    628  
    629             ll mul = 1;
    630             if(cur[n] == 0) mul = cur[0] + 1;
    631  
    632             if(zerocnt > 0) cout << 0 << '\n';
    633             else cout << ((prod * fac[cur[0]]) % mod * (val * mul % mod + sum)) % mod << '\n';
    634         }
    635     }
    636  
    637     return 0;
    638 }
    639 ```
    640 
    641 **Rate The Problem!**
    642 
    643 * Best Problem
    644 * Good Problem
    645 * Okay Problem
    646 * Bad Problem
    647 * Didn't Solve
    648 
    649 #### [2226G - Stop Spot](/contest/2226/problem/G "Codeforces Round 1095 (Div. 2)")
    650 
    651 Idea: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm")   
    652  Preparation: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm"), [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever")   
    653  Solution: [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm")
    654 
    655 **Solution**
    656 
    657 **1. Analysis: where can palindromes appear?**
    658 
    659 Let the final array be:
    660 
    661 $ b = a_1,a_2,...,a_n,p_1,p_2,...,p_m $
    662 
    663 where $p$ is a permutation of $[1,m]$.
    664 
    665 Notice that every newly created even-length palindrome can only be of one type:
    666 
    667 * the palindrome crosses the boundary between $a$ and $p$;
    668 * its symmetry axis must lie on the $a$ side, or exactly on the boundary between $a$ and $p$.
    669 
    670 The number of even-length palindromes completely inside $a$ is fixed. It can be computed by Manacher in $O(n)$ time, and it is independent of the permutation $p$.
    671 
    672 So we only need to count:
    673 
    674 > For each permutation $p$, how many extra even-length palindromes crossing the boundary are created.
    675 
    676 **2. Describing the structure as S+ palindromic suffix**
    677 
    678 Consider an even-length palindrome crossing the boundary.
    679 
    680 It must have the following form:
    681 
    682 $ S + R + rev(S) $
    683 
    684 where:
    685 
    686 * $R$ is an even-length palindromic suffix of $a$, possibly empty;
    687 * $S$ is the segment immediately to the left of $R$;
    688 * $rev(S)$ must appear as a prefix of the permutation $p$.
    689 
    690 Since $p$ is a permutation, its prefix cannot contain duplicate characters.
    691 
    692 Therefore, all characters in $S$ must also be pairwise distinct.
    693 
    694 Thus, for every even-length palindromic suffix $R$, we extend to the left from the position immediately before $R$, and take a locally longest segment $S$ whose characters are pairwise distinct.
    695 
    696 Then we insert $rev(S)$ into a Trie.
    697 
    698 During insertion, every time we pass through a Trie node, we increase the counter of that node by one.
    699 
    700 The meaning is:
    701 
    702 > If the prefix of a permutation reaches this Trie node, then it matches at least one valid $S+$ palindromic suffix structure, so it creates one extra boundary-crossing even-length palindrome.
    703 
    704 Thus, a path in the Trie with pairwise distinct characters corresponds to a prefix of some permutation $p$.
    705 
    706 More specifically, if the prefix of a permutation $p$ walks along a path in the Trie, then the number of boundary-crossing palindromes it creates is the sum of counters on that path.
    707 
    708 **3. Why the number of Trie nodes is O(n)**
    709 
    710 At first glance, every even-length palindromic suffix may extend a segment $S$ to the left and insert it into the Trie, so the total length may look large.
    711 
    712 However, the total inserted length is actually $O(n)$.
    713 
    714 The key claim is:
    715 
    716 > Each position $a_i$ enters the Trie at most twice.
    717 
    718 Proof sketch:
    719 
    720 Consider two even-length palindromic suffix structures:
    721 
    722 $ S_1 + R_1 $
    723 
    724 and
    725 
    726 $ S_2 + R_2 $
    727 
    728 where $R_1, R_2$ are both palindromic suffixes of $a$, $|R_2| \gt |R_1|$, $S_1, S_2$ are the distinct-character segments extended to their left, and $S_1, S_2$ have an intersection (sharing at least one $a_i$).
    729 
    730 Since both suffixes $R_1, R_2$ are palindromes, by the periodicity lemma of strings, these two palindromes induce a period whose length is $|R_2|-|R_1|$.
    731 
    732 The key observation is, since $S_1$ is a segment with pairwise distinct characters, $S_1∩R_2$ cannot be long.
    733 
    734 If the length of $S_1∩R_2$ is greater than $2$, for example, it is $3$, a structure like the following would appear:
    735 
    736 $ ABCABCABC... $
    737 
    738 This contradicts the fact that $R_1,R_2$ are palindromes.
    739 
    740 Therefore, if the $S_1,S_2$ parts of two structures $S_1+R_1$ and $S_2+R_2$ overlap, then $R_1,R_2$ can only be in two very special forms:
    741 
    742 * $AA...AA$ type;
    743 * $AB...AB$ type.
    744 
    745 Now extend this conclusion to three structures.
    746 
    747 If some position $a_i$ entered three different $S$ segments, then every pair of these structures would have to satisfy the special restriction above.
    748 
    749 However, three different palindromic suffixes satisfying this restriction at the same time would force duplicate characters to appear inside some $S$.
    750 
    751 This contradicts the fact that $S$ is a locally longest segment with pairwise distinct characters.
    752 
    753 Therefore, the total number of characters inserted into the Trie is:
    754 
    755 $ O(n) $
    756 
    757 **4. Counting the contribution of each permutation**
    758 
    759 We perform DFS on the Trie.
    760 
    761 Suppose we are currently at Trie node $u$:
    762 
    763 * the current depth is $dep$, meaning the length of the already fixed prefix of the permutation;
    764 * the sum of counters on the current path is $sum$;
    765 * there are still $m-dep$ numbers not placed;
    766 * the number of non-empty children of $u$ is $child(u)$.
    767 
    768 If the next number is chosen as one of the Trie children, then the permutation prefix can still continue matching the Trie, and the contribution is handled by that child.
    769 
    770 If the next number is not a Trie child, then the permutation prefix leaves the Trie from this position.
    771 
    772 Once it leaves the Trie, no matter how the remaining numbers are arranged, no new boundary-crossing palindrome will be created.
    773 
    774 Therefore, at node $u$, we need to count the contribution of going to an empty child.
    775 
    776 The number of empty children is:
    777 
    778 $ (m-dep) - child(u) $
    779 
    780 For each empty child, the remaining $m-dep-1$ numbers can be arranged arbitrarily, so the number of corresponding permutations is:
    781 
    782 $ ((m-dep)-child(u)) \cdot (m-dep-1)! $
    783 
    784 All these permutations have the same number of boundary-crossing palindromes, namely the current $sum$.
    785 
    786 So we add:
    787 
    788 $ cnt[sum] += ((m-dep)-child(u)) \cdot (m-dep-1)! $
    789 
    790 Then for every non-empty child $v$, we continue DFS:
    791 
    792 $ dfs(v, dep+1, sum+w_v) $
    793 
    794 where $w_v$ is the counter stored at Trie node $v$.
    795 
    796 If $dep=m$, then a complete permutation has already been formed, so we directly add:
    797 
    798 $ cnt[sum] += 1 $
    799 
    800 Finally, if a permutation creates $x$ boundary-crossing palindromes, then its total number of even-length palindromes is:
    801 
    802 $ base+x $
    803 
    804 Therefore:
    805 
    806 $ f(base+x)=cnt[x] $
    807 
    808 The answer is:
    809 
    810 $ \sum_x cnt[x]^{base+x+1} $
    811 
    812 taken modulo $998244353$.
    813 
    814 The overall complexity is:
    815 
    816 $ O(n+m) $
    817 
    818 Since $m \le n$, the complexity of each test case can also be regarded as $O(n)$.
    819 
    820 **Implementation**
    821 
    822 ```
    823 #include <bits/stdc++.h>
    824 #define int long long
    825 #define ll long long
    826 #define pii pair<int,int>
    827 #define fi first
    828 #define se second 
    829 using namespace std;
    830  
    831 vector<int> manacher_odd(vector<int> s) {
    832     int n = s.size();
    833     s.insert(s.begin(),-2); 
    834     s.push_back(-3); 
    835     vector<int> p(n + 2);
    836     int l = 0, r = 1;
    837     for(int i = 1; i <= n; i++) {
    838         p[i] = min(r - i, p[l + (r - i)]);
    839         while(s[i - p[i]] == s[i + p[i]]) {
    840             p[i]++;
    841         }
    842         if(i + p[i] > r) {
    843             l = i - p[i], r = i + p[i];
    844         }
    845     }
    846     return vector<int>(begin(p) + 1, end(p) - 1);
    847 }
    848  
    849 vector<int> manacher(vector<int> s) {
    850     vector<int> t;
    851     for(auto c: s) {
    852         t.push_back(-1);
    853         t.push_back(c); 
    854     }
    855     t.push_back(-1); 
    856     auto res = manacher_odd(t);
    857     return vector<int>(begin(res) + 1, end(res) - 1);
    858 }
    859  
    860 struct node {
    861     int count = 0; 
    862     unordered_map<int, node> m; 
    863     node() {
    864         count = 0; 
    865     }
    866 };
    867  
    868 void add(node &current, vector<int> &a, int d) {
    869     current.count++; 
    870     if (d>=a.size()) return; 
    871     if (current.m.find(a[d])!=current.m.end()) {
    872         add(current.m[a[d]],a,d+1);
    873     }
    874     else {
    875         node h;
    876         current.m[a[d]]=h; 
    877         add(current.m[a[d]],a,d+1); 
    878     }
    879 }
    880  
    881 const int mod = 998244353, MX=1e6+4; 
    882 int F[MX]; 
    883 unordered_map<int,int> counts; 
    884  
    885 void init() {
    886     F[0]=1;
    887     for (int i = 1; i < MX; i++) F[i]=F[i-1]*i%mod; 
    888 }
    889  
    890 int pw(int b, int e=mod-2) {
    891     int x=1;
    892     while (e) {
    893         if (e%2) x=x*b%mod;
    894         b=b*b%mod;
    895         e/=2;
    896     }
    897     return x; 
    898 }
    899  
    900 void dfs(node &current, int cur, int d) {
    901     if (!d) {
    902         counts[cur]++;
    903         return; 
    904     }
    905     else (counts[cur]+=F[d-1]*(d-current.m.size()))%=mod; 
    906     for (auto [i, n]:current.m) {
    907         dfs(n, cur+n.count, d-1); 
    908     }
    909 }
    910  
    911 void solve() {
    912     int n, m; cin >> n >> m; 
    913     vector<int> v(n);
    914     for (int &r:v) cin >> r; 
    915     auto t=manacher(v); 
    916     // for (int r:t) cout << r << " "; cout << "\n"; 
    917     int cur=0;
    918     vector<int> prev(m+1,n), nxt(n); 
    919     for (int i = n-1; ~i; i--) {
    920         nxt[i]=prev[v[i]];
    921         prev[v[i]]=i; 
    922     }
    923     node head; 
    924     for (int i = 1; i < n; i++) {
    925         int k=t[2*i-1]/2;
    926         cur+=k;  
    927         if (k<n-i) continue; 
    928         vector<int> a; 
    929         for (int j = i-(n-i)-1; j >= 0; j--) {
    930             if (nxt[j]<=i-(n-i)-1) break;
    931             a.push_back(v[j]); 
    932         }
    933         add(head,a,0); 
    934     }
    935     vector<int> a; 
    936     for (int j = n-1; ~j; j--) {
    937         if (nxt[j]<n) break;
    938         a.push_back(v[j]);
    939     }
    940     add(head,a,0); 
    941     counts.clear(); 
    942     dfs(head,cur,m); 
    943     int ans=0;
    944     for (auto [i,c]:counts) {
    945         // cout << i << " " << c << "\n"; 
    946         ans=(ans+pw(c,i+1))%mod;
    947     }
    948     cout << ans << "\n"; 
    949 }
    950  
    951 int32_t main() {
    952     ios::sync_with_stdio(0); cin.tie(0);
    953     init(); 
    954     int t=1; cin >> t;
    955     while (t--) solve(); 
    956 }
    957 ```
    958 
    959 **Rate The Problem!**
    960 
    961 * Best Problem
    962 * Good Problem
    963 * Okay Problem
    964 * Bad Problem
    965 * Didn't Solve