2154.md (44652B)
1 Source: https://codeforces.com/blog/entry/147471 2 3 Thank you for participating! 4 5 Special thanks to [reirugan](/profile/reirugan "Master reirugan") for writing the analysis for **B, D, E** and to [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") and [Friedrich](/profile/Friedrich "Master Friedrich") for helping to optimise **F1**, leading to the creation of **F2**. 6 7 **Rating Predictions** 8 9 | Problem | A | B | C1 | C2 | D | E | F1 | F2 | 10 | --- | --- | --- | --- | --- | --- | --- | --- | --- | 11 | [reirugan](/profile/reirugan "Master reirugan") | 800 | 1100 | 1200 | 1600 | 1700 | 2000 | 2200 | ¯\_(ツ)_/¯ | 12 | [eric899](/profile/eric899 "Pupil eric899") | 800 | 1000 | 1300 | ¯\_(ツ)_/¯ | 1600 | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ | 13 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1100 | 1500 | 1900 | 1600 | 2100 | 2300 | 2600 | 14 | [_istil](/profile/_istil "Grandmaster _istil") | 800 | 1100 | 1400 | 1800 | 1800 | 2100 | 2000 | 2500 | 15 | [anango](/profile/anango "International Master anango") | 800 | 1100 | 1300 | 1900 | 1800 | 2200 | 2400 | 2700 | 16 | [FetFot](/profile/FetFot "Master FetFot") | 800 | 1100 | 1400 | 1800 | 1900 | ¯\_(ツ)_/¯ | 2400 | ¯\_(ツ)_/¯ | 17 | [Intellegent](/profile/Intellegent "International Master Intellegent") | 800 | 1000 | 1300 | 1900 | 1800 | 2300 | 2200 | 2800 | 18 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 1000 | 1200 | 1800 | 1800 | 2400 | 2500 | 2800 | 19 | [satyam343](/profile/satyam343 "Candidate Master satyam343") | 800 | 1000 | 1400 | 1900 | 1800 | 2400 | 2500 | 2700 | 20 | [catgirl](/profile/catgirl "Master catgirl") | 800 | 1000 | 1300 | 1700 | 1500 | 2200 | 2200 | 2700 | 21 | [wuhudsm](/profile/wuhudsm "Master wuhudsm") | 800 | 1100 | 1400 | 2000 | 1600 | 2200 | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ | 22 | [Edeeva](/profile/Edeeva "Candidate Master Edeeva") | 800 | 900 | 1100 | 1800 | 1700 | 2300 | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ | 23 | Actual rating | 800 | 1000 | 1400 | 2000 | 1900 | 2500 | 2700 | 3300 | 24 25 [2154A - Notelock](/contest/2154/problem/A "Codeforces Round 1060 (Div. 2)"): 26 27 **Hint 1** 28 29 If there is a subarray containing $k - 1$ zeros, then the next element cannot be prevented from being hit. So any time we see $k - 1$ zeros follwed by a one then the one must be protected. 30 31 **Solution** 32 33 From Hint 1, lets protect every $\mathtt{1}$ that fits the pattern. Furthermore we should always protect the first $1$ in the string so lets do that. It turns out that this is all that we need to do, to prove this think inductively: every element that is not protected will always have a $\mathtt{1}$ in the last $k - 1$ elements and so it will be unchanged. So to solve the problem we can check the distance between each consecutive $\mathtt{1}$, if the gap is at least $k$ then add $1$ to the answer. Final time complexity $O(n)$. 34 35 **Implementation(C++)** 36 37 ``` 38 #include<bits/stdc++.h> 39 using namespace std; 40 typedef long long ll; 41 #define debug(x) cout << #x << " = " << x << "\n"; 42 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 43 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 44 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 45 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 46 47 void solve(){ 48 int n, k; 49 cin >> n >> k; 50 51 string s; 52 cin >> s; 53 54 int ans = 0; 55 int last = -1e9; 56 for (int i = 0; i < n; i++){ 57 if (s[i] == '1' && i - last >= k) 58 ans++; 59 if (s[i] == '1') 60 last = i; 61 } 62 63 cout << ans << "\n"; 64 } 65 66 int main(){ 67 ios::sync_with_stdio(false); 68 cin.tie(0); 69 70 int t; 71 cin >> t; 72 while (t--) solve(); 73 } 74 ``` 75 76 **Implementation(Minecraft)** 77 78 <https://youtu.be/5Xku9F6Rbqo> 79 80 [2154B - Make it Zigzag](/contest/2154/problem/B "Codeforces Round 1060 (Div. 2)"): 81 82 **Hint 1** 83 84 You want odd-indexed values to be small, and even-indexed values to be large. In other words, it is beneficial to apply operation 1 on even indices, and operation 2 on odd indices. 85 86 **Hint 2** 87 88 Since operation 1 is free, you may as well apply it to every even index. None of the operations can increase a prefix max, so you can't possibly do any better than just applying operation 1 immediately to every even index. 89 90 **Solution** 91 92 Let's first apply operation 1 to every even index. Now, we can't further increase any even-indexed values, so we just need to decrease odd-indexed values by using operation 2. All of the odd indices are independent from one another, so let's just consider each one separately. For a fixed odd index $i$, the number of instances of operation 2 needed to make it smaller than $a_{i-1}$ and $a_{i+1}$ is given by $\max(0, a_i - \min(a_{i-1}, a_{i+1}) + 1)$. (Be careful with indices $1$ and $n$ as well; you can treat the out of bounds values as being arbitrarily large, or just take care of them separately.) Now, we sum this value, across all odd indices $i$. 93 94 **Implementation(C++)** 95 96 ``` 97 #include<bits/stdc++.h> 98 using namespace std; 99 typedef long long ll; 100 #define debug(x) cout << #x << " = " << x << "\n"; 101 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 102 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 103 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 104 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 105 106 void solve(){ 107 int n; 108 cin >> n; 109 110 vector<int> a(n); 111 for (int &x : a) cin >> x; 112 113 vector<int> pre(n); 114 pre[0] = a[0]; 115 for (int i = 1; i < n; i++) 116 pre[i] = max(pre[i - 1], a[i]); 117 118 ll ans = 0; 119 for (int i = 0; i < n; i += 2){ 120 int dif = -1; 121 if (i > 0) 122 dif = max(dif, a[i] - pre[i - 1]); 123 124 if (i < n - 1) 125 dif = max(dif, a[i] - pre[i + 1]); 126 127 ans += dif + 1; 128 } 129 130 cout << ans << "\n"; 131 } 132 133 int main(){ 134 ios::sync_with_stdio(false); 135 cin.tie(0); 136 137 int t; 138 cin >> t; 139 while (t--) solve(); 140 } 141 ``` 142 143 [2154C1 - No Cost Too Great (Easy Version)](/contest/2154/problem/C1 "Codeforces Round 1060 (Div. 2)"): 144 145 **Hint 1** 146 147 You can make an element divisible by $2$ in $1$ move. 148 149 **Hint 2** 150 151 Can you check if the answer is $0$ or if the answer is $1$? 152 153 **Solution** 154 155 By result of Hint 1, the answer cannot be more than $2$, as we can always pick two elements and make them both divisible by $2$ using at most $1$ move on each. So now we just need to check if the answer is $0$ or $1$. 156 157 To check if the answer is $0$, we need to determine if there is a common divisor between two elements. Note that it is sufficient to only check if there is a common prime divisor. So, for each element, iterate through all its prime divisors and check if there is another element with the same prime divisor. 158 159 To check if the answer is $1$, we can do the same as $0$. This time, for each $i$ we check if $a_i + 1$ shares a common prime divisor with another element. 160 161 Prime divisors can be pre-calculated with the Sieve of Eratosthenes in $O(N\log\log N)$ where $N$ is the maximum possible element (so $2 \cdot 10^5$ for this problem). However, the constraints are lenient enough to allow $O(n\sqrt{N})$ as well. 162 163 The final complexity comes out to $O(n\omega(N) + N\log\log N)$, where $\omega(x)$ is used to denote the number of distinct prime divisors of $x$. Note that the editorial implementation is $O(n\omega(N)\log(n\omega(N)) + N\log\log N)$ due to use of c++ std::map for the sake of readability. 164 165 **Implementation(C++)** 166 167 ``` 168 #include<bits/stdc++.h> 169 using namespace std; 170 typedef long long ll; 171 #define debug(x) cout << #x << " = " << x << "\n"; 172 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 173 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 174 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 175 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 176 177 const int N = 2e5 + 10; 178 vector<vector<int>> pfac(N + 1); 179 180 void solve(){ 181 int n; 182 cin >> n; 183 184 vector<int> a(n), b(n); 185 for (int &x : a) cin >> x; 186 for (int &x : b) cin >> x; 187 188 int ans = 2; 189 map<int, int> cnt; 190 for (int i = 0; i < n; i++){ 191 for (int x : pfac[a[i]]){ 192 if (cnt[x] > 0) 193 ans = 0; 194 cnt[x]++; 195 } 196 } 197 198 for (int i = 0; i < n; i++){ 199 for (int x : pfac[a[i]]) 200 cnt[x]--; 201 202 for (int x : pfac[a[i] + 1]){ 203 if (cnt[x] > 0) 204 ans= min(ans, 1); 205 } 206 207 for (int x : pfac[a[i]]) 208 cnt[x]++; 209 } 210 211 cout << ans << "\n"; 212 } 213 214 int main(){ 215 ios::sync_with_stdio(false); 216 cin.tie(0); 217 218 for (int i = 2; i <= N; i++){ 219 if (!pfac[i].empty()) 220 continue; 221 222 for (int j = i; j <= N; j += i) 223 pfac[j].push_back(i); 224 } 225 226 int t; 227 cin >> t; 228 while (t--) solve(); 229 } 230 ``` 231 232 [2154C2 - No Cost Too Great (Hard Version)](/contest/2154/problem/C2 "Codeforces Round 1060 (Div. 2)"): 233 234 **Hint 1** 235 236 Solve the easy version. 237 238 **Hint 2** 239 240 We can always make two elements $i, j$ divisible by $2$ with no more than $b_i + b_j$ cost. 241 242 **Hint 3** 243 244 By hint 2, we should never perform more than one operation on more than one element. 245 246 **Solution** 247 248 Lets say we are trying to make the elements at index $i, j$ have a common divisor. From hint 2 and 3 there are only two cases to consider here. The first case where we make $0$ or $1$ operation on both $i$ and $j$. Or the second case where we make more than $1$ operation on a single element. We should never do more than $1$ operation on both elements because we can always do better by making both elements divisible by $2$. 249 250 So now to solve the problem on the entire array, we should try to solve both of the cases. For convenience lets reorder the elements so that $b$ is in sorted order. 251 252 The first case can be solve almost identically to the easy version of the problem. We can always do at least as good as $b_1 + b_2$, the only other possibility is only making one operation. To do this we just check if $a_i + 1$ has a common prime divisor with another element. 253 254 The second case is the more tricky case, we need to check the optimal way to make more than one operations for each element, and it is probably the crux of the problem. The key thing to notice is that we actually do not need to check every element, in fact we can only check the element with the smallest value of $b_i$ ($b_1$ because $b$ is sorted). To prove this lets argue by contradiction, supposed we made $k$ ($k \ge 2$) operations on element $x$ ($x \ge 2$). The total cost of this is $k \cdot b_x$, we know from hint 2 that we can do $b_1 + b_x$ or better, since $b_1$ is the smallest element we know that $b_1 + b_x \le k \cdot b_x$ and thus we do not need to consider this case! 255 256 So now we need to quickly check what is the optimal way to use multiple operations on the first element. To do this we can iterate through all the prime divisors of the other elements and determine the minimum number of operations to make $a_1$ divisible by it. 257 258 The final time complexity comes out to $O(n\omega(N) + N\log\log N)$, where $\omega(x)$ is used to denote the number of distinct prime divisors of $x$. Note that the editorial implementation is $O(n\omega(N)\log(n\omega(N)) + N\log\log N)$ due to use of c++ std::map for the sake of readability. 259 260 **Implementation(C++)** 261 262 ``` 263 #include<bits/stdc++.h> 264 using namespace std; 265 typedef long long ll; 266 #define debug(x) cout << #x << " = " << x << "\n"; 267 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 268 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 269 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 270 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 271 272 const int N = 2e5 + 10; 273 vector<vector<int>> pfac(N + 1); 274 275 void solve(){ 276 int n; 277 cin >> n; 278 279 vector<int> a(n), b(n); 280 for (int &x : a) cin >> x; 281 for (int &x : b) cin >> x; 282 283 vector<int> ord(n); 284 iota(ord.begin(), ord.end(), 0); 285 sort(ord.begin(), ord.end(), [&](int x, int y) -> bool{ 286 return b[x] < b[y]; 287 }); 288 289 int ans = b[ord[0]] + b[ord[1]]; 290 map<int, int> cnt; 291 for (int i = 0; i < n; i++){ 292 for (int x : pfac[a[i]]){ 293 if (cnt[x] > 0) 294 ans = 0; 295 cnt[x]++; 296 } 297 } 298 299 for (int i = 0; i < n; i++){ 300 for (int x : pfac[a[i]]) 301 cnt[x]--; 302 303 for (int x : pfac[a[i] + 1]){ 304 if (cnt[x] > 0) 305 ans= min(ans, b[i]); 306 } 307 308 for (int x : pfac[a[i]]) 309 cnt[x]++; 310 } 311 312 int idx = ord[0]; 313 vector<int> check; 314 for (int i = 0; i < n; i++){ 315 if (i == idx) 316 continue; 317 318 for (int x : pfac[a[i]]) 319 check.push_back(x); 320 } 321 322 for (int x : check){ 323 int times = x - (a[idx] % x); 324 if (times == x) 325 times = 0; 326 327 ans = min(1LL * ans, 1LL * times * b[idx]); 328 } 329 330 cout << ans << "\n"; 331 } 332 333 int main(){ 334 ios::sync_with_stdio(false); 335 cin.tie(0); 336 337 for (int i = 2; i <= N; i++){ 338 if (!pfac[i].empty()) 339 continue; 340 341 for (int j = i; j <= N; j += i) 342 pfac[j].push_back(i); 343 } 344 345 int t; 346 cin >> t; 347 while (t--) solve(); 348 } 349 ``` 350 351 [2154D - Catshock](/contest/2154/problem/D "Codeforces Round 1060 (Div. 2)"): 352 353 **Hint 1** 354 355 Destroying a leaf will never split the tree. 356 357 **Hint 2** 358 359 Trees are bipartite. In particular, you can root the tree arbitrarily, then partition vertices into those with even depth and those with odd depth. All edges connect an even depth vertex to an odd depth vertex. 360 361 **Solution** 362 363 We would like to decrease the size of the tree by one vertex using no more than three moves. To do so, we will pick an arbitrary leaf $v$ and destroy it. However, we must make sure that we do not destroy the vertex we are standing on, and that we do not have two consecutive instances of the second instruction. To do so, let's root the tree arbitrarily, and color vertices with even depth red and vertices with odd depth blue. We maintain the color of the vertex we are standing on, noting that every instance of instruction 1 flips the color. Now, if we are standing on the same color as $v$, we apply operation 1 once. Otherwise, we apply operation 1 twice. Thus, we are not currently standing on leaf $v$, so now we can destroy $v$. Since we applied at least one instance of instruction 1, we do not have two consecutive instances of instruction 2. By iterating this process until the only remaining vertex is vertex $n$, we guarantee that we have reached vertex $n$. 364 365 **Implementation(C++)** 366 367 ``` 368 #include<bits/stdc++.h> 369 using namespace std; 370 typedef long long ll; 371 #define debug(x) cout << #x << " = " << x << "\n"; 372 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 373 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 374 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 375 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 376 377 void solve(){ 378 int n; 379 cin >> n; 380 381 vector<vector<int>> g(n); 382 for (int i = 0; i < n - 1; i++){ 383 int u, v; 384 cin >> u >> v; 385 u--; 386 v--; 387 388 g[u].push_back(v); 389 g[v].push_back(u); 390 } 391 392 vector<int> dep(n), par(n), ch(n); 393 auto dfs = [&](auto self, int c, int p) -> void{ 394 if (p != -1) 395 dep[c] = dep[p] + 1; 396 par[c] = p; 397 398 for (int x : g[c]){ 399 if (x == p) continue; 400 401 self(self, x, c); 402 ch[c]++; 403 } 404 }; 405 dfs(dfs, n - 1, -1); 406 407 array<vector<int>, 2> leaves; 408 leaves[0]; 409 410 for (int i = 0; i < n; i++){ 411 if (ch[i] == 0) 412 leaves[dep[i] & 1].push_back(i); 413 } 414 415 vector<array<int, 2>> ans; 416 int col = dep[0] & 1; 417 for (int i = 0; i < n - 1; i++){ 418 if (leaves[col ^ 1].empty()){ 419 ans.push_back({1, -1}); 420 col ^= 1; 421 } 422 423 int nxt = leaves[col ^ 1].back(); 424 leaves[col ^ 1].pop_back(); 425 ans.push_back({2, nxt}); 426 427 int p = par[nxt]; 428 ch[p]--; 429 if (ch[p] == 0) 430 leaves[dep[p] & 1].push_back(p); 431 432 ans.push_back({1, -1}); 433 col ^= 1; 434 } 435 436 cout << ans.size() << "\n"; 437 for (auto [x, y] : ans){ 438 if (x == 1) 439 cout << "1\n"; 440 else 441 cout << "2 " << y + 1 << "\n"; 442 } 443 } 444 445 int main(){ 446 ios::sync_with_stdio(false); 447 cin.tie(0); 448 449 int t; 450 cin >> t; 451 while (t--) solve(); 452 } 453 ``` 454 455 **Bonus** 456 457 Can you implement the checker? 458 459 [2154E - No Mind To Think](/contest/2154/problem/E "Codeforces Round 1060 (Div. 2)"): 460 461 **Hint 1** 462 463 Without loss of generality, assume the array is sorted. Let's fix $x = 2y+1$, and let's also fix the median of a given operation $a_i$, for some $y+1 \leq i\leq n-y$. Now, we see that the best subsequence to choose is $a_1, a_2, \dots, a_y, a_i, a_{i+1}, \dots, a_{i+y}$, because we must choose $y$ values to the left of $a_i$ and $y$ values to the right of $a_i$, and we would like to change the smallest values possible. 464 465 **Hint 2** 466 467 Suppose you have applied one operation with median $a_i$ and another operation with median $a_j$, for $y+1 \leq i \lt j \leq n-y$. Now, you have increased up to $\min(2y, j-1)$ of the smallest values to either $a_i$ or $a_j$, since you can increase up to $y$ values smaller than the median each operation. However, you have also decreased $y$ values after $a_i$, and $y$ values after $a_j$. Instead, you might as well have just applied two operations with median $a_j$, which allows you to increase $\min(2y, j-1)$ of the smallest values to $a_j$, and decrease only the $y$ values after $a_j$. Therefore, there exists some optimal sequence of operations where we use the same median across all operations. 468 469 **Solution** 470 471 By the result of Hint 2, there exists some optimal sequence of operations where we use the same median across all operations. Let's fix the median at $a_i$. Now, if we choose $x = 2y+1$ for some $0\leq y \leq \min(i-1, n-i)$, we are able to increase the values of $a_1, a_2, \dots, a_{\min(ky, i-1)}$ to $a_i$, but we must also decrease the values of $a_{i+1}, a_{i+2}, \dots, a_{i+y}$ to $a_i$. 472 473 The benefits of increasing $y$ are that we can increase more values, but notice that these benefits are getting less and less, because we are increasing values that are already larger. For example, the benefit of increasing $y$ from $0$ to $1$ is that now we can increase the values $a_1, a_2, \dots, a_k$, but the benefit from increasing $y$ from $1$ to $2$ is that now we can increase the values $a_{k+1}, a_{k+2}, \dots, a_{2k}$; increasing $y$ from $1$ to $2$ is not as beneficial as increasing $y$ from $0$ to $1$, because the values we are increasing are already relatively big. (There's a small case to think about, when $ky$ first exceeds $i-1$, but note that the number of values you can increase is also monotonically decreasing, so this doesn't cause any issues.) The same reasoning goes for the losses. The losses of increasing $y$ are that we are forced to decrease more values, and these losses are getting greater and greater. If we increase $y$ from $0$ to $1$, we are only forced to decrease $a_{i+1}$, but if we increase $y$ from $1$ to $2$, we now have to decrease $a_{i+2}$, which is worse because $a_{i+2}$ is relatively big. In other words, our net gains (that is, the benefits minus the losses) are monotonically decreasing. 474 475 We want to keep incrementing $y$ as long as our net gains are positive, then stop incrementing $y$ once our net gains become negative. Since our net gains are monotonically decreasing, we can binary search for this point. (Alternative solutions might use ternary search instead.) So we iterate over all choices of $i$, then binary search for the optimal choice of $y$, which in total takes $O(n\log{n})$ time. Note that all computations can be done quickly with prefix sums. 476 477 **Implementation(C++)** 478 479 ``` 480 #include<bits/stdc++.h> 481 using namespace std; 482 typedef long long ll; 483 #define debug(x) cout << #x << " = " << x << "\n"; 484 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 485 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 486 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 487 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 488 489 void solve(){ 490 int n, k; 491 cin >> n >> k; 492 493 vector<int> a(n); 494 for (int &x : a) cin >> x; 495 496 sort(a.begin(), a.end()); 497 498 vector<ll> pre(n); 499 pre[0] = a[0]; 500 for (int i = 1; i < n; i++) 501 pre[i] = pre[i - 1] + a[i]; 502 503 ll ans = pre[n - 1]; 504 505 auto query = [&](int l, int r) -> ll{ 506 ll res = pre[r]; 507 if (l > 0) 508 res -= pre[l - 1]; 509 return res; 510 }; 511 512 for (int i = 0; i < n; i++){ 513 int l = 1, r = min(i, n - i - 1) + 1; 514 while (l < r){ 515 int mid = (l + r) / 2; 516 517 int left = min(1LL * (mid - 1) * k, 1LL * i); 518 int right = min(1LL * mid * k - 1, 1LL * i); 519 ll cost = query(left, right) + a[i + mid]; 520 if (cost <= 1LL * a[i] * (right - left + 1 + 1)) 521 l = mid + 1; 522 else 523 r = mid; 524 } 525 l--; 526 if (l == 0) 527 continue; 528 529 int right = min(1LL * l * k - 1, 1LL * i); 530 ll len = right + 1 + l; 531 ll cost = len * a[i] - (query(0, right) + query(i + 1, i + l)); 532 ans = max(ans, pre[n - 1] + cost); 533 } 534 535 cout << ans << "\n"; 536 } 537 538 int main(){ 539 ios::sync_with_stdio(false); 540 cin.tie(0); 541 542 int t; 543 cin >> t; 544 while (t--) solve(); 545 } 546 ``` 547 548 [2154F1 - Bombing (Easy Version)](/contest/2154/problem/F1 "Codeforces Round 1060 (Div. 2)"): 549 550 **Hint 1** 551 552 For every valid permutation we can always determine the index $k$ used as the split in the riffle shuffle operation, unless it is the sorted permutation. 553 554 **Hint 2** 555 556 Find the number of riffle shuffles for each split. 557 558 **Solution** 559 560 Lets prove Hint 1. For a valid permutation $q$, consider the first $k$ such that $k$ appers after $k + 1$ in $q$, if $q$ is a riffle shuffle of $[1, 2, \ldots, n]$ then we know that $k$ must be the split used. The only permutation where such a item does not exist is the one where the permutation is already sorted. 561 562 Now lets try finding the number of solutions for a specific split point $k$ in sub-quadratic time. We can think of it like this, colour all the numbers less than or equal to $k$ in blue and the elements bigger than $k$ in red. Now when we replace all $-1$ in $p$ the following must be true after, for each blue element $x$ exactly $x$ elements are blue in its prefix and for each red element $x$ exactly $x - k$ elements are red in its prefix. So now we just need to count the number of ways to insert red and blue elements so that this condition is satisfied. To find this iterate over each index that is not $-1$ and insert the number of elements of its colour that it demands and fill the remaining elements in its prefix with the other colour. This will have worst case $O(n)$ run time if we can calculate the required binomial coefficients in $O(1)$ which can be done by pre-calculating factorials. 563 564 So we can just iterate over each split and sum in $O(n^2)$ making sure to remember that we might overcount the sorted permutation. 565 566 **Implementation(C++)** 567 568 ``` 569 #include<bits/stdc++.h> 570 using namespace std; 571 typedef long long ll; 572 #define debug(x) cout << #x << " = " << x << "\n"; 573 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 574 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 575 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 576 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 577 578 const int MOD = 998244353; 579 580 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged 581 struct modnum { 582 static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); 583 584 using S = conditional_t<is_big_mod, ll, int>; 585 using L = conditional_t<is_big_mod, __int128, ll>; 586 587 S x; 588 589 modnum() : x(0) {} 590 modnum(ll _x) { 591 _x %= static_cast<ll>(mod); 592 if (_x < 0) { _x += mod; } 593 x = _x; 594 } 595 596 modnum pow(ll n) const { 597 modnum res = 1; 598 modnum cur = *this; 599 while (n > 0) { 600 if (n & 1) res *= cur; 601 cur *= cur; 602 n /= 2; 603 } 604 return res; 605 } 606 modnum inv() const { return (*this).pow(mod-2); } 607 608 modnum& operator+=(const modnum& a){ 609 x += a.x; 610 if (x >= mod) x -= mod; 611 return *this; 612 } 613 modnum& operator-=(const modnum& a){ 614 if (x < a.x) x += mod; 615 x -= a.x; 616 return *this; 617 } 618 modnum& operator*=(const modnum& a){ 619 x = static_cast<L>(x) * a.x % mod; 620 return *this; 621 } 622 modnum& operator/=(const modnum& a){ return *this *= a.inv(); } 623 624 friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } 625 friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } 626 friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } 627 friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } 628 629 friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } 630 friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } 631 friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } 632 633 friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } 634 friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } 635 }; 636 637 using mint = modnum<MOD>; 638 639 struct Combi{ 640 vector<mint> _fac, _ifac; 641 int n; 642 643 Combi() { 644 n = 1; 645 _fac.assign(n + 1, 1); 646 _ifac.assign(n + 1, 1); 647 } 648 649 void check_size(int m){ 650 int need = n; 651 while (need < m) need *= 2; 652 m = need; 653 if (m <= n) return; 654 655 _fac.resize(m + 1); 656 _ifac.resize(m + 1); 657 for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1]; 658 659 _ifac[m] = _fac[m].inv(); 660 for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1); 661 n = m; 662 } 663 664 mint fac(int m){ 665 check_size(m); 666 return _fac[m]; 667 } 668 669 mint ifac(int m){ 670 check_size(m); 671 return _ifac[m]; 672 } 673 674 mint ncr(int n, int r){ 675 if (n < r || r < 0) return 0; 676 677 return fac(n) * ifac(n - r) * ifac(r); 678 } 679 680 mint npr(int n, int r){ 681 if (n < r || r < 0) return 0; 682 683 return fac(n) * ifac(n - r); 684 } 685 } comb; 686 687 void solve(){ 688 int n; 689 cin >> n; 690 691 vector<int> a(n); 692 for (int &x : a) { 693 cin >> x; 694 if (x != -1) 695 x--; 696 } 697 698 mint ans = 0; 699 700 for (int i = 0; i < n - 1; i++){ 701 mint res = 1; 702 int spaces = 0; 703 int less = -1; 704 int more = i; 705 for (int j = 0; j < n; j++){ 706 if (a[j] == -1){ 707 spaces++; 708 continue; 709 } 710 711 if (a[j] <= i){ 712 int need = a[j] - less - 1; 713 res *= comb.ncr(spaces, need); 714 more += spaces - need; 715 less = a[j]; 716 717 } 718 719 if (a[j] > i){ 720 int need = a[j] - more - 1; 721 res *= comb.ncr(spaces, need); 722 less += spaces - need; 723 more = a[j]; 724 } 725 726 spaces = 0; 727 } 728 729 res *= comb.ncr(spaces, i - less); 730 731 ans += res; 732 } 733 734 bool sorted = true; 735 for (int i = 0; i < n; i++){ 736 if (a[i] != i && a[i] != -1) 737 sorted = false; 738 } 739 740 if (sorted) 741 ans -= n - 2; 742 cout << ans << "\n"; 743 } 744 745 int main(){ 746 ios::sync_with_stdio(false); 747 cin.tie(0); 748 749 int t; 750 cin >> t; 751 while (t--) solve(); 752 } 753 ``` 754 755 [2154F2 - Bombing (Hard Version)](/contest/2154/problem/F2 "Codeforces Round 1060 (Div. 2)"): 756 757 **Step 1** 758 759 Solve the easy version. 760 761 **Step 2** 762 763 If $p_i \lt i$ we know that $p_i$ must belong to the left side of the split, similarly if $p_i \gt i$ we know that $p_i$ must belong to the right side of the split. 764 765 **Step 3** 766 767 If a permutation p is a riffle shuffle of $[1,2,\ldots,n]$, then it will have three regions described by two integers $l, r$ as follows: 768 769 * a prefix where for all $i$ ($1 \le i \le l$) we have $p_i = i$. 770 * a suffix where for all $i$ ($r \le i \le n$) we have $p_i = i$. 771 * a middle region where for all $i$ ($l \lt i \lt r$) we have $p_i \ne i$. 772 773 See that the first region will all belong to the left side of the split, and the last region will all belong to the right side of the split. Additionally, we can deduce the side of the entire middle region from Step 2. There is a single edge case to this where $p$ is the sorted permutation. 774 775 **Step 4** 776 777 Suppose there is an index $i$ where $a_i \ne i$ and $a_i \ne -1$, or in other words, the sorted permutation is not valid. In this case, from Step 3, we can deduce the side of every element $i$ where $a_i \ne -1$. 778 779 **Step 5** 780 781 For the opposite case to Step 4 (i.e, the case where the sorted permutation is valid), can you think of a way to solve this? 782 783 **Step 5.1** 784 785 Can you find a closed form formula for the case where $p_i = -1$ for all $i$? 786 787 **Step 5.2** 788 789 There is almost a bijection between colouring an array in two colours and valid riffle shuffles of $[1,2,\ldots,n]$ with the sole edge case being the sorted permutation, which is counted $n - 1$ times, if we account for this we obtain the formula $2^n - n$. 790 791 **Step 5.3** 792 793 Now that we have a formula, from Step 3 we should just find the number of ways to fill each run of consecutive $-1$, leaving everything outside as the prefix and suffix as discussed in Hint 3. Solving a consecutive run of $-1$ is equivalent to solving the case in Step 5.1 on a smaller array. So we just solve each of these runs and sum to get the answer for this case. 794 795 **Step 6** 796 797 Now lets solve the same case as Step 4. For each $k$, consider a consecutive run of $-1$ and try to find the number of ways to fill it, lets try to find some nice properties for some cases. Let me introduce some notation, I will type each gap in the following way: 798 799 * an $l \rightarrow l$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the left side of the split. 800 * an $l \rightarrow r$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the right side of the split. 801 * similar notation for $r \rightarrow l$ and $r \rightarrow r$. 802 803 Now notice that for any $k$, the number of ways to fill an $l \rightarrow l$ or $r \rightarrow r$ gap will always be the same. 804 805 **Step 7** 806 807 For the $l \rightarrow r$ and $r \rightarrow l$ gaps, we have to get a bit more creative. The key thing to notice is that each $k$ will demand a unique number of elements from the left side of the split to be placed inside the gap. Now since the number of left elements must be between $0$ and the size of the gap, we can restrict the number of $k$ we need to consider to no more than the size of the gap! 808 809 **Step 8** 810 811 For each gap, calculate this range of valid $k$, and take the intersection of all the ranges. Now if we use a very similar implementation to the easy version of the problem but only consider $k$ within this range, and skipping $l \rightarrow l$ and $r \rightarrow r$ gaps by calculating their contribution separately, the problem will be solved. Since, say, the range of valid $k$ has size $x$, then the number of $l \rightarrow r$ and $r \rightarrow l$ gaps will be no more than approximately $n/x$, and so the final time complexity is $O(x \cdot n/x)$, which is $O(n)$. 812 813 **Implementation(C++)** 814 815 ``` 816 #include<bits/stdc++.h> 817 using namespace std; 818 typedef long long ll; 819 #define debug(x) cout << #x << " = " << x << "\n"; 820 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 821 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 822 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 823 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 824 825 const int MOD = 998244353; 826 827 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged 828 struct modnum { 829 static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); 830 831 using S = conditional_t<is_big_mod, ll, int>; 832 using L = conditional_t<is_big_mod, __int128, ll>; 833 834 S x; 835 836 modnum() : x(0) {} 837 modnum(ll _x) { 838 _x %= static_cast<ll>(mod); 839 if (_x < 0) { _x += mod; } 840 x = _x; 841 } 842 843 modnum pow(ll n) const { 844 modnum res = 1; 845 modnum cur = *this; 846 while (n > 0) { 847 if (n & 1) res *= cur; 848 cur *= cur; 849 n /= 2; 850 } 851 return res; 852 } 853 modnum inv() const { return (*this).pow(mod-2); } 854 855 modnum& operator+=(const modnum& a){ 856 x += a.x; 857 if (x >= mod) x -= mod; 858 return *this; 859 } 860 modnum& operator-=(const modnum& a){ 861 if (x < a.x) x += mod; 862 x -= a.x; 863 return *this; 864 } 865 modnum& operator*=(const modnum& a){ 866 x = static_cast<L>(x) * a.x % mod; 867 return *this; 868 } 869 modnum& operator/=(const modnum& a){ return *this *= a.inv(); } 870 871 friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } 872 friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } 873 friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } 874 friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } 875 876 friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } 877 friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } 878 friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } 879 880 friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } 881 friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } 882 }; 883 884 using mint = modnum<MOD>; 885 886 struct Combi{ 887 vector<mint> _fac, _ifac; 888 int n; 889 890 Combi() { 891 n = 1; 892 _fac.assign(n + 1, 1); 893 _ifac.assign(n + 1, 1); 894 } 895 896 void check_size(int m){ 897 int need = n; 898 while (need < m) need *= 2; 899 m = need; 900 if (m <= n) return; 901 902 _fac.resize(m + 1); 903 _ifac.resize(m + 1); 904 for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1]; 905 906 _ifac[m] = _fac[m].inv(); 907 for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1); 908 n = m; 909 } 910 911 mint fac(int m){ 912 check_size(m); 913 return _fac[m]; 914 } 915 916 mint ifac(int m){ 917 check_size(m); 918 return _ifac[m]; 919 } 920 921 mint ncr(int n, int r){ 922 if (n < r || r < 0) return 0; 923 924 return fac(n) * ifac(n - r) * ifac(r); 925 } 926 927 mint npr(int n, int r){ 928 if (n < r || r < 0) return 0; 929 930 return fac(n) * ifac(n - r); 931 } 932 } comb; 933 934 void solve(){ 935 int n; 936 cin >> n; 937 938 vector<int> a(n); 939 for (int &x : a) { 940 cin >> x; 941 if (x != -1) 942 x--; 943 } 944 945 bool fixed = true; 946 for (int i = 0; i < n; i++) 947 if (a[i] != -1 && a[i] != i) 948 fixed = false; 949 950 if (fixed){ //case where all a[i] != -1 has a[i] = i 951 vector<mint> prod(n + 1); 952 prod[0] = 1; 953 for (int i = 1; i <= n; i++) 954 prod[i] = prod[i - 1] * 2; 955 956 int last = -1; 957 mint ans = 0; 958 for (int i = 0; i <= n; i++){ 959 if (i == n || a[i] != -1){ 960 int len = i - last - 1; 961 ans += prod[len] - len - 1; 962 last = i; 963 } 964 } 965 966 ans += 1; 967 cout << ans << "\n"; 968 return; 969 } 970 971 vector<bool> side(n); 972 bool found = false; 973 for (int i = 0; i < n; i++){ 974 if (a[i] == -1) 975 continue; 976 977 if (a[i] < i) 978 side[i] = false; // left side 979 if (a[i] > i) 980 side[i] = true; // right side 981 if (a[i] == i) 982 side[i] = found; 983 if (a[i] != i) 984 found = true; 985 } 986 987 int last = -1; 988 vector<array<int, 2>> ranges; 989 for (int i = 0; i < n; i++){ 990 if (a[i] == -1) 991 continue; 992 993 if (last == -1){ 994 last = i; 995 continue; 996 } 997 998 if (side[i] && !side[last]){ // left -> right gap 999 int mn = last - a[last]; // min right already placed 1000 int mx = mn + i - last; // max right already placed 1001 ranges.push_back({a[i] - mx, a[i] - mn + 1}); 1002 } 1003 1004 if (!side[i] && side[last]){ // right -> left gap 1005 int mx = i - a[i]; // max right placed by last 1006 int mn = mx - (i - last); // min right placed by last 1007 ranges.push_back({a[last] - mx, a[last] - mn + 1}); 1008 } 1009 1010 last = i; 1011 } 1012 1013 int l = 0, r = n - 1; 1014 for (auto [u, v] : ranges){ 1015 l = max(l, u); 1016 r = min(r, v); 1017 } 1018 1019 mint coef = 1; 1020 vector<mint> score(n); // score[i] = contribution when splitting at i 1021 for (int i = l; i <= r; i++) 1022 score[i] = 1; 1023 1024 last = -1; 1025 for (int i = 0; i < n; i++){ 1026 if (a[i] == -1) 1027 continue; 1028 1029 bool prev = false; 1030 if (last != -1) 1031 prev = side[last]; 1032 int spaces = i - last - 1; 1033 1034 if (side[i] && prev || !side[i] && !prev){ 1035 int cnt = 0; 1036 if (last == -1) 1037 cnt = a[i]; 1038 else 1039 cnt = a[i] - a[last] - 1; 1040 1041 coef *= comb.ncr(spaces, cnt); 1042 } 1043 1044 if (side[i] && !prev){ // left -> right 1045 for (int j = l; j <= r; j++){ 1046 int placed = 0; 1047 if (last != -1) 1048 placed = last - a[last]; // how many right i have placed by last 1049 1050 int need = a[i] - (j + placed); // j + placed is the next one i need to place after last 1051 score[j] *= comb.ncr(spaces, need); 1052 } 1053 } 1054 1055 if (!side[i] && prev){ // right -> left 1056 for (int j = l; j <= r; j++){ 1057 int big = i - a[i] + j - 1; // last right to be placed by i 1058 1059 int need = big - a[last]; 1060 score[j] *= comb.ncr(spaces, need); 1061 } 1062 } 1063 1064 last = i; 1065 } 1066 1067 for (int j = l; j <= r; j++){ 1068 if (!side[last]){ 1069 score[j] *= comb.ncr(n - last - 1, j - a[last] - 1); 1070 } 1071 else{ 1072 score[j] *= comb.ncr(n - last - 1, n - 1 - a[last]); 1073 } 1074 } 1075 1076 mint ans = 0; 1077 for (int i = 0; i < n; i++) 1078 ans += score[i]; 1079 ans *= coef; 1080 cout << ans << "\n"; 1081 } 1082 1083 int main(){ 1084 ios::sync_with_stdio(false); 1085 cin.tie(0); 1086 1087 int t; 1088 cin >> t; 1089 while (t--) solve(); 1090 } 1091 ``` 1092 1093 Bonus editorial by [Friedrich](/profile/Friedrich "Master Friedrich"): 1094 1095 **Solution 2** 1096 1097 **Hint 1** 1098 1099 Can you uniquely determine, for each element $a[i]$, which subsequence it belongs to? 1100 1101 **Hint 2** 1102 1103 For which values of $k$ does a solution exist? 1104 1105 **Solution** 1106 1107 Let the subsequence on indices $1$ to $k$ be $L$ and the subsequence on indices $k+1$ to $n$ be $R$. 1108 1109 For every $a[i]\in L$ we have $a[i]-i\le 0$, since there must be exactly $a[i]-1$ elements of $L$ before position $i$. Symmetrically, for every $a[i]\in R$ we have $a[i]-i\ge 0$. 1110 1111 From the same observation, if $a[i]\in L$ then there must be exactly $i-a[i]$ indices $j \lt i$ with $a[j]\in R$. This lets us decide the side of each element except when $a[i]=i$, which is ambiguous. Once there exists some $a[j]\ne j$, the counts of elements in $L$ and $R$ to the left and right are constrained and cannot both decrease, so within any interval between fixed points $a[i]=i$ both types $L$ and $R$ must appear unless the whole interval consists of fixed points. 1112 1113 **First case.** There are positions with $a[i]=i$. Consider the gaps between consecutive fixed points. In a gap of size $m$ between indices $i$ and $j$ with $a[i]=i$ and $a[j]=j$, we can count the valid assignments of the elements $i+1,\dots,j-1$ to $L$ or $R$. Summing over all possible splits gives $\binom{m}{0}+\binom{m}{1}+\cdots+\binom{m}{m-1}=2^{m-1}.$ To avoid overcounting the fully ordered arrangement, for each gap of size $m$ we count $2^{m-1}-m-1$, and then add $1$ at the end for the completely ordered sequence. 1114 1115 **Second case.** Every element can be assigned unambiguously to $L$ or $R$. Add a sentinel $a[0]=0$ and assign it to $L$. Track $n+1$ dynamic states $(i,j)$ with initial states $(1,1),(1,2),\dots,(1,n+1)$, where $i$ is the next index needed in $L$ and $j$ is the next index needed in $R$. Each state stores the number of ways to reach it, initially $1$. 1116 1117 Updating every state at every step would be too slow, so only update at gap boundaries. There are two subcases for a gap of size $m$: 1118 1119 1. The endpoints of the gap belong to the same side. For each state, we know how many of the $m$ elements, say $k$, must go to that side, so we multiply the state’s count by $\binom{m}{k}$ and advance $(i,j)$ accordingly by $k$ and $m-k$. 1120 2. The endpoints belong to different sides. First apply any deferred updates. Now either $i$ or $j$ is identical across all current states because the last element before the gap was forced to $L$ or $R$. For a gap of size $m$ there are at most $m$ next states, and for each we can compute the number of shuffles since the counts assigned to $L$ and $R$ are fixed. This gives $O(m)$ work per gap, hence $O(n)$ overall. 1121 1122 This completes the counting in $O(n)$ time. 1123 1124 **Implementation(Python)** 1125 1126 ``` 1127 import sys 1128 input = sys.stdin.readline 1129 MOD = 998244353 1130 1131 fac_arr = [1] 1132 finv_arr = [1] 1133 1134 def enlarge_fac(): 1135 old_size = len(fac_arr) 1136 new_size = old_size * 2 1137 for i in range(old_size, new_size + 1): 1138 fac_arr.append((fac_arr[-1] * i) % MOD) 1139 ifac = [pow(fac_arr[-1], -1, MOD)] 1140 for i in range(new_size, old_size,-1): 1141 ifac.append((ifac[-1] * i) % MOD) 1142 ifac.reverse() 1143 for x in ifac: 1144 finv_arr.append(x) 1145 1146 def fac(n): 1147 while n >= len(fac_arr): enlarge_fac() 1148 return fac_arr[n] 1149 1150 def finv(n): 1151 while n >= len(finv_arr): enlarge_fac() 1152 return finv_arr[n] 1153 1154 def binom(n, k): 1155 if k < 0 or k > n: return 0 1156 return ((fac(n) * finv(k)) % MOD * finv(n - k)) % MOD 1157 for _ in range(int(input())): 1158 n = int(input()) 1159 a = list(map(int, input().split())) + [n+1] 1160 if max([0 if a[i] == -1 else abs(a[i]-i-1) for i in range(n)]) == 0: 1161 sol = 1 1162 last = 0 1163 for i in a: 1164 if i >= 0: 1165 sol += pow(2, i - last - 1, MOD) - 1 - (i - last - 1) 1166 last = i 1167 sol %= MOD 1168 print(sol) 1169 else: 1170 S = [(0,i,1) for i in range(1,n)] 1171 last = -1 1172 left = 1 1173 eq = 0 1174 pl = 0 1175 mult = 1 1176 lastv = 0 1177 nd = 0 1178 for idx in range(n+1): 1179 if a[idx] == -1: continue 1180 gap = idx - last - 1 1181 at = 0 1182 if idx + 1 > a[idx] or (idx + 1 == a[idx] and eq == 0): 1183 if idx + 1 > a[idx]: eq = 1 1184 at = 1 1185 else: eq = 1 1186 TMP = [] 1187 if at ^ left: 1188 for i,j,k in S: 1189 if left: j += pl; i = nd 1190 else: i += pl; j = nd 1191 if left: rev = a[idx] - j - 1 1192 else: rev = a[idx] - i - 1 1193 if left: i += gap - rev 1194 else: j += gap - rev 1195 if at: i = a[idx] 1196 else: j = a[idx] 1197 f = binom(gap,rev) 1198 if f: TMP.append((i,j,(k*f)%MOD)) 1199 left ^= 1 1200 pl = 0 1201 lastv = a[idx] 1202 nd = a[idx] 1203 S = TMP 1204 else: 1205 rev = a[idx] - lastv - 1 1206 pl += gap - rev 1207 nd = a[idx] 1208 lastv = a[idx] 1209 mult *= binom(gap,rev) 1210 mult %= MOD 1211 last = idx 1212 print(((sum([x[-1] for x in S])%MOD)*mult)%MOD) 1213 ```