2247.md (27012B)
1 Source: https://codeforces.com/blog/entry/155337 2 3 Thank you for participating in the round! 4 5 [2247A - Zero Sum](/contest/2247/problem/A "Codeforces Round 1111 (Div. 2)") 6 7 * Idea: [PvPro](/profile/PvPro "International Grandmaster PvPro") 8 * Solution: [PvPro](/profile/PvPro "International Grandmaster PvPro") 9 10 **Hints** 11 12 **Hint 1** 13 14 Try to find an invariant 15 16 **Hint 2** 17 18 Consider the sum of all elements in the array 19 20 **Solution** 21 22 It's easy to see that $\left( \sum\limits_{i = 1}^n a_i \right) \bmod 4$ does not change after a single operation. Therefore, if $\left( \sum\limits_{i = 1}^n a_i \right) \bmod 4 \neq 0$, then the answer is "NO". 23 24 Otherwise, let's make $a_1 = 1, a_2 = -1, a_3 = 1, \dots, a_{n - 1} = (-1)^n$. We can always do that by performing operations with indices $1, 2, 3, \dots n - 1$ in this order, and after operation number $i$ we set the $i$-th element to the value we want. After that, $| \sum\limits_{i = 1}^n a_i | \leq 2$, so it is equal to zero because it's the only number divisible by $4$ in that range. 25 26 **Code** 27 28 ``` 29 #include <iostream> 30 31 using namespace std; 32 33 void solve() { 34 int n; cin >> n; 35 int sm = 0; 36 for (int i = 0; i < n; i++) { 37 int x; cin >> x; 38 sm += x; 39 } 40 41 cout << (abs(sm) % 4 == 0 ? "YES\n" : "NO\n"); 42 } 43 44 int main() { 45 int t; 46 cin >> t; 47 while (t--) { 48 solve(); 49 } 50 return 0; 51 } 52 ``` 53 54 **Rate The Problem!** 55 56 * Good Problem 57 * Okay Problem 58 * Bad Problem 59 * Didn't Solve 60 61 [2247B - Yet Another Constructive](/contest/2247/problem/B "Codeforces Round 1111 (Div. 2)") 62 63 * Idea: [PvPro](/profile/PvPro "International Grandmaster PvPro") 64 * Solution: [PvPro](/profile/PvPro "International Grandmaster PvPro") 65 66 **Hints** 67 68 **Hint 1** 69 70 When is the answer "NO"? 71 72 **Hint 2** 73 74 The answer is "NO" when $k \gt m$ 75 76 **Solution** 77 78 If $m \lt k$, then the answer is $-1$ because it is well known that in any array with $m$ elements there is a subarray with sum divisible by $m$. Here is a proof: Consider remainders of prefix sums by $m$. There are $m + 1$ prefix sums, and only $m$ possible remainders by modulo $m$, therefore two of the prefix sums have the same remainder and in the segment between these two prefix sums the sum is divisible by $m$. 79 80 Otherwise, the solution is to make $a_j = 1$ for all $j$ such that $j \mod k \neq 0$, and $a_j = m - k + 1$ for $j \mod k \equiv 0$. In this construction, every subarray of length $k$ has the sum of exactly $m$, and every subarray whose length is less than $k$ obviously has a sum that is greater than $0$ and less than $m$, therefore it can't be divisible by $m$. 81 82 **Code** 83 84 ``` 85 #include <bits/stdc++.h> 86 using namespace std; 87 88 int main() { 89 ios::sync_with_stdio(false); 90 cin.tie(nullptr); 91 92 int t; 93 cin >> t; 94 while (t--) { 95 int n, k, m; 96 cin >> n >> k >> m; 97 98 if (k > m) { 99 cout << "NO\n"; 100 continue; 101 } 102 103 cout << "YES\n"; 104 for (int i = 0; i < n; i++) { 105 cout << (i % k == 0 ? m - k + 1 : 1) << ' '; 106 } 107 cout << '\n'; 108 } 109 return 0; 110 } 111 ``` 112 113 **Rate The Problem!** 114 115 * Good Problem 116 * Okay Problem 117 * Bad Problem 118 * Didn't Solve 119 120 [2247C - Inversion of a Subsequence](/contest/2247/problem/C "Codeforces Round 1111 (Div. 2)") 121 122 * Idea: [PvPro](/profile/PvPro "International Grandmaster PvPro"), [makrav](/profile/makrav "Legendary Grandmaster makrav") 123 * Solution: [PvPro](/profile/PvPro "International Grandmaster PvPro") 124 125 **Hints** 126 127 **Hint 1** 128 129 The answer is either $-1$, or it is $\leq 2$ 130 131 **Solution** 132 133 If $a = b$, the answer is $0$. If $a$ contains no $1$-s in it, the answer is $-1$ because we can't make any operation. Also, if $b$ doesn't have any $0$ values, then we can't get $b$ from any array in one operation, because all values on changed positions should be $0$ before the operation, but their sum would be even in this case. 134 135 If neither of these conditions holds, the answer is always $1$ or $2$. It's easy to check whether the answer is $1$: just consider the positions where $a_j \neq b_j$, and check if we can do an operation with exactly this set of indices. Otherwise, the answer is $2$. 136 137 Here is a proof: if in the set of indices where $a_j \neq b_j$ there are $\geq 2$ indices where $a_j = 1$, we can just split these wrong indices into two sets with odd sums of $a_j$. Otherwise, all values that should be changed in array $a$ are $0$. Also, there are indices $i$ and $k$ such that $a_i = b_i = 0$ and $a_k = b_k = 1$ just because the answer is not $-1$. So let's make the first operation with a subsequence which includes all wrong indices (where $a_j \neq b_j$) and indices $i$ and $k$. The operation is possible because the sum of all $a$ values is $1$. After this operation, we can make an operation with only two elements, $i$ and $k$. After these two operations, $a = b$. 138 139 **Code** 140 141 ``` 142 #include <bits/stdc++.h> 143 using namespace std; 144 145 int main() { 146 ios::sync_with_stdio(false); 147 cin.tie(nullptr); 148 149 int t; 150 cin >> t; 151 while (t--) { 152 int n; 153 cin >> n; 154 155 vector<int> a(n), b(n); 156 for (int &x : a) cin >> x; 157 for (int &x : b) cin >> x; 158 159 if (a == b) { 160 cout << 0 << '\n'; 161 continue; 162 } 163 164 int sum = 0; 165 166 for (int i = 0; i < n; ++i) { 167 if (a[i] != b[i]) { 168 sum += a[i]; 169 } 170 } 171 172 if (accumulate(a.begin(), a.end(), 0) == 0 || accumulate(b.begin(), b.end(), 0) == n) { 173 cout << -1 << "\n"; 174 continue; 175 } 176 177 if (sum % 2 == 1) { 178 cout << 1 << '\n'; 179 } else { 180 cout << 2 << '\n'; 181 } 182 } 183 184 return 0; 185 } 186 ``` 187 188 **Rate The Problem!** 189 190 * Good Problem 191 * Okay Problem 192 * Bad Problem 193 * Didn't Solve 194 195 [2247D1 - XOR Sorting (Easy Version)](/contest/2247/problem/D1 "Codeforces Round 1111 (Div. 2)") 196 197 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav") 198 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav") 199 200 **Hints** 201 202 **Hint 1** 203 204 Imagine you only need to swap elements on some positions $i$ and $j$. What is the minimum $k$ such that you can do it with all XORs of indices $\leq k$ 205 206 **Hint 2** 207 208 The answer is always zero or a power of two. 209 210 **Solution** 211 212 It is inefficient to perform swaps whose index XOR is not a power of two. 213 214 Suppose we want to swap $a_i$ and $a_j$ $(i \lt j)$, and $i \oplus j$ is not a power of two. Let $b$ be the highest differing bit in numbers $i$ and $j$. Then perform the following swaps in order: $(i, i + 2^b), (i + 2^b, j), (i, i + 2^b)$. It's easy to see that $i \oplus (i + 2^b) = 2^b$, however, $(i + 2^b) \oplus j$ might not be a power of two. In this case, we want to replace this swap recursively with the same procedure with a sequence of swaps, such that each of which has an XOR equal to a power of $2$. It's easy to see that after performing these swaps, the only change in the array is that elements on positions $i$ and $j$ are swapped. 215 216 Now we want to solve the problem. How do we check whether we can sort the array using only operations with XOR at most $2^j$? Let's split the array into contiguous blocks of elements with size $2^{j + 1}$ (the size of the last block may be less than $2^{j+1}$). It's easy to see that each element will remain in its original block after any number of swaps with XOR $\leq 2^j$. And within a single block, we can obtain any permutation of its elements just because we can always do any swap inside the block with some sequence of swaps $\leq 2^j$. Therefore, we only need to check whether sorting every contiguous block of $2^{j + 1}$ elements, the array becomes sorted. 217 218 We can simplify that by only considering two values, $min_j$ and $max_j$, which correspond to the maximum and minimum elements in block $j$. Then we want to check that $ \forall j \; | \; max_j \leq min_{j + 1}$ holds. 219 220 For the simple version of this task, we can check it naively in $O(n \log n)$ because there are $O(log n)$ different possible answers, and each one of them can be checked in $O(n)$. 221 222 **Code** 223 224 ``` 225 #include <bits/stdc++.h> 226 #include <cassert> 227 228 using namespace std; 229 using ll = long long; 230 231 #define all(x) (x).begin(), (x).end() 232 #define sz(x) (int)(x).size() 233 #define pb push_back 234 235 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 236 237 void solve() { 238 int n, q; cin >> n >> q; 239 vector<int> a(n); 240 for (auto &u : a) cin >> u; 241 if (is_sorted(all(a))) { 242 cout << "0\n"; 243 return; 244 } 245 for (int x = 0;; x++) { 246 int mx = -1; 247 bool good = 1; 248 for (int j = 0; j * (1 << (x+1)) < n; j++) { 249 int cmx = -1; 250 for (int i = 0; j * (1<<(x+1)) + i < n && i < (1<<(x+1)); i++) { 251 int cur = a[j *(1<<(x+1)) + i]; 252 good &= (mx <= cur); 253 cmx = max(cmx, cur); 254 } 255 mx = max(mx, cmx); 256 } 257 if (good) { 258 cout << (1<<x) << '\n'; 259 return; 260 } 261 } 262 } 263 264 signed main() { 265 cin.tie(0)->sync_with_stdio(false); 266 int tt = 1; 267 cin >> tt; 268 269 while (tt--) { 270 solve(); 271 } 272 273 return 0; 274 } 275 ``` 276 277 **Rate The Problem!** 278 279 * Good Problem 280 * Okay Problem 281 * Bad Problem 282 * Didn't Solve 283 284 [2247D2 - XOR Sorting (Hard Version)](/contest/2247/problem/D2 "Codeforces Round 1111 (Div. 2)") 285 286 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav") 287 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav") 288 289 **Hints** 290 291 **Hint 1** 292 293 There are a lot of powers of two mentioned in the solution. Which data structure is usually built on an array of a size of a power of two? 294 295 **Hint 2** 296 297 Use the segment tree. 298 299 **Solution** 300 301 First, read the solution for the problem D1. 302 303 In the hard version, we need to also handle queries. Let us append several $\infty$ values to the end of the array so that its length becomes a power of two. Then let's build a segment tree over this array. Now each node of the segment tree corresponds to a block. In each vertex of segment tree we want to maintain the following three values: -maximum value on the segment -minimum value on the segment -minimum $k$ needed to sort the segment 304 305 It is easy to compute the values of a node from the values of its children: maximum and minimum are trivial, and for $k$ we need to take maximum among our two children, and if $max_L \gt min_R$ we need to increase $k$ to length of the segment divided by two. ($max_L$ is the maximum in the left son, and $min_R$ is the minimum in the right son). 306 307 This solution works in $O(n + q \log n)$ time. 308 309 **Code** 310 311 ``` 312 #include <bits/stdc++.h> 313 #include <cassert> 314 315 using namespace std; 316 using ll = long long; 317 318 #define all(x) (x).begin(), (x).end() 319 #define sz(x) (int)(x).size() 320 #define pb push_back 321 322 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 323 324 void solve() { 325 int n, q; cin >> n >> q; 326 vector<int> a(n); 327 for (auto &u : a) cin >> u; 328 int N = 1; 329 while (N < n) N *= 2; 330 while (n < N) { 331 a.pb(1e9); 332 n++; 333 } 334 vector<array<int, 3>> t(2 * n); 335 vector<int> L(2 * n, 1); 336 for (int j = 0; j < n; j++) t[n + j] = {a[j], a[j], 0}; 337 auto pull= [&](int j, int len) { 338 t[j][0] = min(t[j << 1][0], t[j << 1 | 1][0]); 339 t[j][1] = max(t[j << 1][1], t[j << 1 | 1][1]); 340 t[j][2] = max(t[j<<1][2], t[j<<1|1][2]); 341 if (t[j<<1][1] > t[j<<1|1][0]) t[j][2] = max(t[j][2], len / 2); 342 }; 343 for (int j = n - 1; j >= 1; j--) { 344 L[j] = 2 * L[j << 1]; 345 pull(j, L[j]); 346 } 347 cout << t[1][2] << '\n'; 348 while (q--) { 349 int p, x; cin >> p >> x; 350 p += n; 351 t[p] = {x, x, 0}; 352 p >>= 1; 353 int len = 2; 354 while (p) { 355 pull(p, len); 356 p >>= 1; 357 len *= 2; 358 } 359 cout << t[1][2] << '\n'; 360 } 361 } 362 363 signed main() { 364 cin.tie(0)->sync_with_stdio(false); 365 int tt = 1; 366 cin >> tt; 367 368 while (tt--) { 369 solve(); 370 } 371 372 return 0; 373 } 374 ``` 375 376 **Rate The Problem!** 377 378 * Good Problem 379 * Okay Problem 380 * Bad Problem 381 * Didn't Solve 382 383 [2247E - Build a Tree](/contest/2247/problem/E "Codeforces Round 1111 (Div. 2)") 384 385 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav") 386 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav") 387 388 **Hints** 389 390 **Hint 1** 391 392 $k$ should be even in order to have an answer 393 394 **Hint 2** 395 396 Try to find lower and upper bounds for $k$ to have an answer. Every even $k$ in this range is achievable. 397 398 **Hint 3** 399 400 Consider a centroid. 401 402 **Solution** 403 404 Thanks to [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik") for sharing this solution! My initial approach was more complicated. 405 406 Consider the centroid of the answer and set it as the root of the tree. Then the sum of distances $\leq 2 \cdot$ (sum of heights of all vertices). It is easy to see that, to maximize the sum of distances, we need to make two roughly equal subtrees with sizes close to $\lfloor \frac{n}{2} \rfloor$, so we now have an upper bound for our answer. The lower bound is obviously $2 \cdot (n - 1)$ because we need to traverse each edge at least twice, because we start at vertex 1 and finish there. From this observation, we can also notice that the answer is always even because, for each edge, we must cross from one side of the edge to the other an even number of times to always come back. 407 408 Now our goal is to build the tree such that after rooting it with its centroid, $2 \cdot$ (sum of heights of vertices) equals the required $x$. Let's start from a tree where the centroid has $n - 1$ direct children. Then we reroot the children one by one until the sum of heights reaches the desired $\frac{x}{2}$. We will also maintain the condition that each subtree's size doesn not exceed the $\lfloor \frac{n}{2} \rfloor$ bound. It is always possible to build such a tree because we know that our answer lies in the range of all possible answers, and we can reroot each vertex not only to the highest vertex from a big subtree, but also to all of its parents, so we can make an increase in the sum of heights by 1, 2, and all numbers up to the current maximum height. 409 410 When we have built our tree, we need to label its vertices to solve the problem. Basically, we need to label vertices in such a way that $\operatorname{dist}(i, (i \bmod n) + 1) = h_i + h_{(i \bmod n) + 1}$, where $h$ corresponds to the array of all vertices' heights. For this to hold, we need to distribute labels so that vertices $i$ and $(i \bmod n) + 1$ end up in different subtrees of the centroid (we will label the centroid as vertex 1 and forget about it because for the centroid the condition holds automatically). 411 412 Now it's a standard problem to put each label into some subtree so that two consecutive labels end up in different subtrees. The approach is to assign labels one by one, and we always try to put the label into the subtree with the maximum number of remaining free spots, also considering the last label's subtree. It's easy to prove by induction that, with the constraint on the size of each subtree, this approach works. 413 414 This can be implemented in $O(n \log n)$ time; however, there are many different possible solutions working in linear time. Also, this problem can be solved under the condition that the tree must be a chain, but I prefer the centroid-based solution. 415 416 **Code** 417 418 ``` 419 #include <bits/stdc++.h> 420 #include <cassert> 421 422 using namespace std; 423 using ll = long long; 424 425 #define all(x) (x).begin(), (x).end() 426 #define sz(x) (int)(x).size() 427 #define pb push_back 428 429 void solve() { 430 ll n, k; cin >> n >> k; 431 ll top = 0; 432 for (int x = 1; x <= n / 2; x++) { 433 top += x; 434 if (2 * x <= n - 1) top += x; 435 } 436 top *= 2; 437 if (k % 2 == 1 || k < 2 * (n - 1) || k > top) { 438 cout << "-1\n"; 439 return; 440 } 441 if (n == 2) { 442 cout << "1 2\n"; 443 return; 444 } 445 vector<int> cnt(2, (n - 1) / 2); 446 if (n % 2 == 0) cnt[1]++; 447 ll cur = top; 448 cur /= 2; 449 k /= 2; 450 for (int i = 0; ; i++) { 451 int id = i % 2; 452 if (cnt[id] > 1 && cur - (cnt[id] - 1) >= k) { 453 cur -= (cnt[id] - 1); 454 cnt.pb(1); 455 cnt[id]--; 456 } else if (cnt[id] > 1 || cur == k) { 457 vector<pair<int, int>> edges; 458 int cr = 2; 459 vector<int> startv(sz(cnt)); 460 for (int j = 0; j < sz(cnt); j++) { 461 startv[j] = cr; 462 if (j != id) { 463 int prv = 1; 464 for (int x = 0; x < cnt[j]; x++) { 465 edges.pb({prv, cr++}); 466 prv = cr - 1; 467 } 468 } else { 469 int prv = 1, start = cr; 470 for (int x = 0; x < cnt[j] - 1; x++) { 471 edges.pb({prv, cr++}); 472 prv = cr - 1; 473 } 474 int was = cnt[j]; 475 int neww = was - (cur - k); 476 if (neww == 1) edges.pb({1, cr++}); 477 else edges.pb({start + (neww - 2), cr++}); 478 } 479 } 480 set<pair<int, int>> st; 481 for (int j = 0; j < sz(cnt); j++) st.insert({cnt[j], j}); 482 vector<int> per(n + 1); 483 per[1] = 1; 484 int lst = -1; 485 for (int x = 2; x <= n; x++) { 486 auto it = --st.end(); 487 while ((*it).second == lst) it--; 488 auto [c,id] = *it; 489 st.erase(it); 490 per[startv[id]] = x; 491 startv[id]++; 492 lst = id; 493 assert(cnt[id] > 0); 494 cnt[id]--; 495 st.insert({cnt[id], id}); 496 } 497 for (auto &[u, v] : edges) { 498 u = per[u]; v = per[v]; 499 cout << u << ' ' << v << '\n'; 500 } 501 break; 502 } 503 } 504 } 505 506 signed main() { 507 int t = 1; 508 cin >> t; 509 510 while (t--) { 511 solve(); 512 } 513 514 return 0; 515 } 516 ``` 517 518 **Rate The Problem!** 519 520 * Good Problem 521 * Okay Problem 522 * Bad Problem 523 * Didn't Solve 524 525 [2247F - Paths on a Grid](/contest/2247/problem/F "Codeforces Round 1111 (Div. 2)") 526 527 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav") 528 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav") 529 530 **Hints** 531 532 **Hint 1** 533 534 Suppose we have two cells in a set. What condition must these two cells satisfy for the set to remain \textit{good}? 535 536 **Hint 2** 537 538 These two cells should have the same set of paths going through them. How can we specify \textit{good} sets then? 539 540 **Hint 3** 541 542 Consider the rightmost path going from $(1, 1)$ to $(i, j)$ and the leftmost path going from $(1, 1)$ to $(i, j)$. Find an intersection of these two paths. 543 544 **Solution** 545 546 First, let us observe that if there is at least one cell in a $\textit{good}$ set of cells through which no path from cell $(1, 1)$ to cell $(n, m)$ passes, then the same is true for all other cells in the set as well. Otherwise, there would exist at least one path contradicting the definition of a $\textit{good}$ set. Therefore, we can immediately add $2^{\text{free}} - 1$ to the answer, where $free$ is the number of free cells through which none of the required paths pass. 547 548 From now on, we consider only those free cells through which at least one required path passes. Suppose our set contains some free cell $(i, j)$ and another cell $(i_1, j_1)$. Notice that one of the following two conditions must hold: $(i_1 \leq i, j_1 \leq j)$ or $(i_1 \geq i, j_1 \geq j)$. This is because at least one required path passes through each of these cells, and if neither condition holds, then such paths cannot coincide, since a path may only move either one cell down or one cell to the right; 549 550 In the first case, $(i_1 \leq i, j_1 \leq j)$, we need the following condition: every path from $(1, 1)$ to $(i, j)$ must pass through cell $(i_1, j_1)$; otherwise, the set is not $\textit{good}$. Similarly, if the second condition $(i_1 \geq i, j_1 \geq j)$ holds, then every path from cell $(i, j)$ to $(n, m)$ must pass through cell $(i_1, j_1)$. 551 552 Therefore, we construct directed edges from cell $(i, j)$ to all cells $(i_1, j_1)$ such that $(i_1 \leq i, j_1 \leq j)$ and every path from $(1, 1)$ to $(i, j)$ passes through $(i_1, j_1)$, and also to all cells satisfying $(i_1 \geq i, j_1 \geq j)$ such that every path from $(i, j)$ to $(n, m)$ passes through $(i_1, j_1)$. Then we find the strongly connected components of this graph. A set of cells is good if and only if all of its cells belong to the same SCC. 553 554 Essentially, such edges mean that every path from $(1, 1)$ to $(n, m)$ passing through $(i, j)$ also passes through $(i_1, j_1)$. This makes it clear that if all cells of the set belong to one SCC, then the set is good; otherwise, it is not. 555 556 Now let us understand how to efficiently find SCCs in this graph. Consider only the edges from cells $(i, j)$ to cells $(i_1, j_1)$ satisfying $(i_1 \leq i, j_1 \leq j)$. Notice that if there exists an edge $(i, j) \rightarrow (i_1, j_1)$ and an edge $(i_1, j_1) \rightarrow (i_2, j_2)$, then there also exists an edge $(i, j) \rightarrow (i_2, j_2)$, because the edge $(i, j) \rightarrow (i_1, j_1)$ means that all paths from $(1, 1)$ to cell $(i, j)$ pass through cell $(i_1, j_1)$. 557 558 We can also observe that all cells reachable by such edges from $(i, j)$ form a path in the directed graph. Therefore, for each cell $(i, j)$ it is sufficient to find the edge to the cell $(i_1, j_1)$ with the maximum value of $i_1 + j_1$. 559 560 We process cells in increasing order of $i + j$. If cell $(i - 1, j)$ is reachable from $(1, 1)$ and cell $(i, j - 1)$ is not reachable from $(1, 1)$, then the required edge goes to cell $(i - 1, j)$. Similarly, if cell $(i - 1, j)$ is not reachable from $(1, 1)$ and cell $(i, j - 1)$ is reachable from $(1, 1)$, then the required edge goes to cell $(i, j - 1)$. 561 562 Otherwise, the required edge goes to the LCA of cells $(i - 1, j)$ and $(i, j - 1)$ in the tree formed by the previously constructed SCC edges. 563 564 Analogously, we can construct edges $(i, j) \rightarrow (i_1, j_1)$ to cells satisfying $i_1 \geq i$ and $j_1 \geq j$. 565 566 Thus, our graph contains only $O(nm)$ edges, and we can easily find its SCCs. 567 568 To answer LCA queries in the tree, we use binary lifting. Therefore, the overall complexity of the solution is $O(nm \log nm)$ time and $O(nm \log nm)$ memory. 569 570 In fact, building SCCs is not even necessary. We can merge two cells $A$ and $B$ in dsu if $A$ is the direct parent of $B$ in a tree built from the cell $(1, 1)$ and if $B$ is the direct parent of $A$ in a tree built from the cell $(n, m)$. 571 572 **Code** 573 574 ``` 575 #include <bits/stdc++.h> 576 #include <cassert> 577 578 using namespace std; 579 using ll = long long; 580 581 #define all(x) (x).begin(), (x).end() 582 #define sz(x) (int)(x).size() 583 #define pb push_back 584 585 const int maxl = 20, maxn = 1e6 + 10; 586 int up[maxl][maxn]; 587 588 constexpr ll mod = 998244353; 589 ll sum(ll x, ll y) { 590 return (x + y >= mod ? x + y - mod : x + y); 591 } 592 ll mul(ll x, ll y) { 593 return (x * y) % mod; 594 } 595 ll diff(ll x, ll y) { 596 return (x >= y ? x - y : x + mod - y); 597 } 598 599 void solve() { 600 int n, m; cin >> n >> m; 601 vector<string> s(n); 602 for (auto &u : s) cin >> u; 603 604 vector<vector<int>> is_path(n, vector<int>(m)); 605 vector<int> h(n * m); 606 vector<vector<int>> g_scc(n * m); 607 for (int j = 0; j < maxl; j++) up[j][0] = 0; 608 auto newv = [&](int v, int p) { 609 g_scc[v].pb(p); 610 h[v] = h[p] + 1; 611 up[0][v] = p; 612 for (int j = 1; j < maxl; j++) up[j][v] = up[j - 1][up[j - 1][v]]; 613 }; 614 auto jump = [&](int v, int where) { 615 for (int j = maxl - 1; j >= 0; j--) { 616 if (((h[v] - where) >> j) & 1) v = up[j][v]; 617 } 618 return v; 619 }; 620 auto lca = [&](int u, int v){ 621 if (h[u] > h[v]) swap(u, v); 622 v = jump(v, h[u]); 623 if (u == v) return u; 624 for (int j = maxl - 1; j >= 0; j--) { 625 if (up[j][v] != up[j][u]) { 626 v = up[j][v]; u = up[j][u]; 627 } 628 } 629 return up[0][v]; 630 }; 631 632 is_path[0][0] = (s[0][0] == '1'); 633 for (int i = 0; i < n; i++) { 634 for (int j = 0; j < m; j++) { 635 if (i == 0 && j == 0) continue; 636 if (s[i][j] == '0') continue; 637 is_path[i][j] = (i > 0 && is_path[i - 1][j]) || (j > 0 && is_path[i][j - 1]); 638 if (is_path[i][j]) { 639 int par; 640 if (i == 0 || !is_path[i - 1][j]) par = i * m + j - 1; 641 else if (j == 0 || !is_path[i][j - 1]) par = (i - 1) * m + j; 642 else par = lca((i - 1) * m + j, i * m + j - 1); 643 newv(i * m + j, par); 644 } 645 } 646 } 647 648 h.assign(n * m, 0); 649 for (int j =0; j < maxl; j++) up[j][n * m - 1] = n * m - 1; 650 vector<vector<int>> is_path2(n, vector<int>(m)); 651 is_path2[n - 1][m - 1] = (s[n - 1][m - 1] == '1'); 652 for (int i = n - 1; i >= 0; i--) { 653 for (int j = m - 1; j >= 0; j--) { 654 if (i == n - 1 && j == m - 1) continue; 655 if (s[i][j] == '0') continue; 656 is_path2[i][j] = (i + 1 < n && is_path2[i + 1][j]) || (j + 1 < m && is_path2[i][j + 1]); 657 if (is_path2[i][j]) { 658 int par; 659 if (i + 1 == n || !is_path2[i + 1][j]) par = i * m + j + 1; 660 else if (j + 1 == m || !is_path2[i][j + 1]) par = (i + 1) * m + j; 661 else par = lca((i + 1) * m + j, i * m + j + 1); 662 newv(i * m + j, par); 663 } 664 } 665 } 666 int cntbad = 0; 667 for (int i = 0; i < n; i++) { 668 for (int j = 0; j < m; j++) cntbad += (!is_path[i][j] || !is_path2[i][j]); 669 } 670 ll ans = 1; 671 for (int j = 0; j < cntbad; j++) ans = mul(ans, 2); 672 ans = diff(ans, 1); 673 // cout << cntbad << endl; 674 675 vector<int> used(n * m), ord; 676 auto dfs = [&](int v, auto&&self) -> void { 677 used[v] = 1; 678 for (int u : g_scc[v]) if (!used[u]) self(u, self); 679 ord.pb(v); 680 }; 681 for (int j =0; j < n * m; j++) { 682 if (!used[j] && is_path[j/m][j % m] && is_path2[j/m][j % m]) dfs(j, dfs); 683 } 684 reverse(all(ord)); 685 vector<bool> is_good(n * m); 686 for (int el : ord) is_good[el] = 1; 687 688 vector<vector<int>> grev(n * m); 689 for (int i = 0; i < n * m; i++) for (int u : g_scc[i]) grev[u].pb(i); 690 vector<int> cnt; 691 used.assign(n * m, 0); 692 auto dfs2 = [&](int v, auto&&self) -> void { 693 cnt.back()++; 694 used[v] = 1; 695 for (int u : grev[v]) { 696 if (!used[u] && is_good[u]) self(u, self); 697 } 698 }; 699 for (int u : ord) { 700 if (!used[u]) { 701 cnt.pb(0); 702 dfs2(u, dfs2); 703 } 704 } 705 for (int c : cnt) { 706 ll cur = 1; 707 for (int j = 0; j < c; j++) cur = mul(cur, 2); 708 ans = sum(ans, diff(cur, 1)); 709 } 710 cout << ans << '\n'; 711 } 712 713 signed main() { 714 int t = 1; 715 cin >> t; 716 717 while (t--) { 718 solve(); 719 } 720 721 return 0; 722 } 723 ``` 724 725 **Rate The Problem!** 726 727 * Good Problem 728 * Okay Problem 729 * Bad Problem 730 * Didn't Solve