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 ¤t, 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 ¤t, 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