1993.md (24767B)
1 Source: https://codeforces.com/blog/entry/132185 2 3 [1993A - Question Marks](/contest/1993/problem/A "Codeforces Round 963 (Div. 2)") 4 5 **Hint** 6 7 What is the pattern of Tim's answer sheet that can give him maximum score? 8 9 **Solution** 10 11 Let's say there are $n$ problems take $A$ as the answer, therefore he can only get $n$ points with the answer $A$. The same is correct for $B$, $C$ and $D$. Therefore, the maximum score can be achieved is $min(n, A) + min(n, B) + min(n, C) + min(n, D)$. 12 13 Time complexity: $O(4n)$ 14 15 **Code (python)** 16 17 ``` 18 t = int(input()) 19 for _ in range(t): 20 n = int(input()) 21 s = input() 22 23 print(sum(min(n, s.count(c)) for c in "ABCD")) 24 ``` 25 26 [1993B - Parity and Sum](/contest/1993/problem/B "Codeforces Round 963 (Div. 2)") 27 28 **Hint 1** 29 30 Find a way to make all the elements even. Then odd. 31 32 **Hint 2** 33 34 In the worst case, the number of operations required is the number of even elements + 1. Why? 35 36 **Solution** 37 38 First, if all elements already have the same parity, we don't need to do perform any operation. 39 40 Next, if the array contains both $even$ and $odd$ numbers. In this case, it is impossible to convert all elements to $even$ numbers. 41 42 **Why?** 43 44 If we apply an operation on: 45 46 * two $odd$ elements, one of them remains $odd$. 47 * two elements of distinct parities, one of them is replaced with their sum, which is an $odd$ number. 48 49 This implies even if we want to change an $odd$ element to $even$ number, it fails in both ways possible. 50 51 So we just want to convert all of them to $odd$ numbers. Now come the greedy part: 52 53 * $even + even = even \longrightarrow$ it doesn't reduce the number of $even$ elements, so skip it. 54 * $odd + odd = even \longrightarrow$ this creates another $even$ number, indeed very awful. 55 * $even + odd = odd \longrightarrow$ this is great, but only if the sum replaces the $even$ one (which means $even \lt odd$). 56 57 Let's find the largest $odd$ element and call it $s$. Then traverse each $even$ elements $t$ in non-decreasing order and apply an operation on $s$ and $t$: 58 59 1. If $t \lt s$, $s+t$ becomes largest odd number. Thus, we set $s := s+t$. This reduce the number of even element by $1$. 60 2. If $t \gt s$, before we do this operation, we need to do another on $s$ and the largest even element to make $s$ the largest in the array. Note that this case only happens at most once. 61 62 As a result, the answer is the number of even elements (plus $1$ if the second case occurs). 63 64 Time complexity: $O(n\log n)$. 65 66 **Code (python)** 67 68 ``` 69 t = int(input()) 70 for _ in range(t): 71 n = int(input()) 72 a = list(map(int, input().split())) 73 74 s = -1 75 v = [] 76 for x in a: 77 if x%2 == 0: 78 v.append(x) 79 elif x > s: 80 s = x 81 v.sort() 82 83 if s == -1 or v == []: 84 print(0) 85 continue 86 87 ans = len(v) 88 for t in v: 89 if t < s: 90 s += t 91 else: 92 ans += 1 93 break 94 95 print(ans) 96 ``` 97 98 [1993C - Light Switches](/contest/1993/problem/C "Codeforces Round 963 (Div. 2)") 99 100 **Hint 1** 101 102 Try to find the segments of moments when a light is on. 103 104 **Hint 2** 105 106 Select this segment from each light. The answer should be the intersection of all of them. 107 108 **Solution** 109 110 > As soon as a chip is installed, it changes the light's status every $k$ minutes. 111 112 Let's first list the segments of the moments when a light is on if we install a chip at moment $x$: 113 114 * $x\rightarrow x+k-1$ 115 * $x+2k\rightarrow x+3k-1$ 116 * $x+4k\rightarrow x+5k-1$ 117 * $\dots$ 118 119 Have you seen the pattern yet? Apparently each segment in the list (except the first one) is actually the segment before it, shifted by $2k$ minutes. This also means that if we divide by $2k$ and take the remainder at both ends of each segment, all these segments become equal. With that, let's call $(a_i\bmod 2k, (a_i+k-1)\bmod 2k)$ the segment of the $i$-th chip. 120 121 Our problem is thus simplified to: find the smallest integer $s$ such that: 122 123 1. $max(a) \le s$ 124 2. $s\bmod 2k$ appears in every segments of all chips. 125 126 In order to satisfy the first condition, it seems if we figure out some $r = s\bmod 2k$ that satisfy the second condition, we may come up with: 127 128 $s = max(a) + ((r - max(a))\bmod 2k)$ 129 130 Next, in order for a segment to contain $r$, this inequality must be satisfied: $r-k+1 \le a_i \le r \pmod{2k}$. This is because a light is on only for at most $k$ minutes (before it gets turned off), so it must come not long before the moment $r$. Let's call $d[z]$ the number of chips that has $a_i \equiv z \pmod{2k}$, then in order for all lights to be on at moment $s$, the condition is: 131 132 $\sum \limits_{z=r-k+1}^{r} d[z] = n$ 133 134 This idea can be implemented using two-pointer technique, that traverse all $r$ from $0$ to $2k-1$. As there can be many possible values of $r$, we only take one that produces $s$ with minimum value. Be careful when handling signs in problems with modules to avoid unnecessary errors. 135 136 Time complexity: $O(n)$. 137 138 **Code (C++)** 139 140 ``` 141 #include <bits/stdc++.h> 142 using namespace std; 143 144 145 const int N = 2e5 + 5; 146 147 int n, k, d[2*N]; 148 149 int main() { 150 cin.tie(0)->sync_with_stdio(0); 151 152 int t; 153 cin >> t; 154 155 while (t--) { 156 cin >> n >> k; 157 158 int mx = -1; 159 fill(d, d + 2*k, 0); 160 161 for (int i = 0; i < n; i++) { 162 int x; 163 cin >> x; 164 assert(x >= 1); 165 d[x % (2*k)]++; 166 mx = max(mx, x); 167 } 168 169 int cnt = 0; 170 int ans = INT_MAX; 171 for (int i = 0; i <= k - 2; i++) { 172 cnt += d[i]; 173 } 174 175 for (int l = 0, r = k-1; l < 2*k; l++, r++) { 176 if (r >= 2*k) r -= 2*k; 177 178 if (cnt += d[r]; cnt == n) { 179 int wait = (r-mx) % (2*k); 180 if (wait < 0) wait += 2*k; 181 ans = min(ans, mx + wait); 182 } 183 184 cnt -= d[l]; 185 } 186 187 if (ans == INT_MAX) { 188 ans = -1; 189 } 190 cout << ans << '\n'; 191 } 192 } 193 ``` 194 195 [1993D - Med-imize](/contest/1993/problem/D "Codeforces Round 963 (Div. 2)") 196 197 **Hint 1** 198 199 Is there any method to calculate median without sorting? 200 201 **Hint 2** 202 203 Is there any relationship between the original array with the final array? 204 205 **Solution** 206 207 Note: in order to explain this solution easier, we'll suppose all arrays are 0-indexed. 208 209 If $n \le k$, we don't have to remove any segment since the statement only tell us to do it while the length of $a$ is greater than $k$. That way, the median of $a$ is fixed. Let's find a way to calculate this value **without** sorting the array. 210 211 Given an integer $x$. If $x$ is less than or equal to the median of $a$, then suppose we sort $a$ in increasing order, $x$ is somewhat to the left of $med(a)$. That means the number of elements greater than or equal to $x$ is more than the number of elements less than $x$. Using this observation, we can create another array $b$ of the same size as $a$, such that $b[i] = 1$ if $a[i] \ge x$, otherwise $b[i] = -1$. The trick here is if $sum(b) \gt 0$, then the condition $x \le med(a)$ is satisfied. Using this trick, we can easily binary search the median of $a$ by fixing value of $x$, checking if $sum(b) \gt 0$ and adjusting the value range of $med(a)$. 212 213 How about $n \gt k$. In this case, we'll keep using the same strategy as above. That is: fix the value of $x$, find a way to delete segments of $a$ so that the array $b$ has largest sum, check if that sum is greater than $0$ and adjust the value range of the answer. 214 215 Note that each time we delete a segment, the size of $a$ is reduced by $k$. We do that until $|a|\le k$. Let's call the final array $a$ after deleting segments $a'$. After some calculation, we come up with $|a'| = ((n-1)\bmod k) + 1$. 216 217 Also, it can be seen that the elements $a'[0], \dots, a'[m-1]$ (where $m = |a'|$) always originate from the elements $a[i_0], \dots, a[i_{m-1}]$ such that $i_0\equiv 0\pmod k, i_1\equiv 1\pmod k, \dots, i_{m-1}\equiv m-1\pmod k$. 218 219 **Why?** 220 221 Suppose we want to delete the segment $[i, i+k-1]$ from $a$. This operation shift all the elements from the right by $k$ units to the left, which means the indexes are subtracted by $k$ units. But if we only care about the indexes modulo $k$ before and after deleting the segments, shifting $k$ units doesn't change their modulos at all. 222 223 With all above observations, we come up with the following DP formula to find the optimal segment deletions: 224 225 * $dp[0] = b[0]$ 226 * If $i\equiv 0\pmod k$ and $i \gt 0$, then $dp[i] = max(dp[i-k], b[i])$ 227 * Otherwise $dp[i] = dp[i-1] + b[i]$. If $i \gt k$ then maximize $dp[i]$ by $dp[i-k]$ 228 229 Then, the maximum sum of $b$ in the optimal deletions equals to $dp[n-1]$. 230 231 Time complexity: $O(n\log max(a))$. 232 233 **Code (C++)** 234 235 ``` 236 #include <bits/stdc++.h> 237 using namespace std; 238 239 const int N = 500005; 240 241 int n, k, a[N]; 242 int dp[N], b[N]; 243 244 bool check(int med) { 245 for (int i = 0; i < n; i++) { 246 if (a[i] >= med) { 247 b[i] = 1; 248 } else { 249 b[i] = -1; 250 } 251 } 252 253 dp[0] = b[0]; 254 for (int i = 1; i < n; i++) { 255 if (i%k == 0) { 256 dp[i] = max(dp[i-k], b[i]); 257 } else { 258 dp[i] = dp[i-1] + b[i]; 259 if (i > k) { 260 dp[i] = max(dp[i], dp[i-k]); 261 } 262 } 263 } 264 265 return dp[n-1] > 0; 266 } 267 268 int main() { 269 cin.tie(0)->sync_with_stdio(0); 270 271 int t; cin >> t; 272 while (t--) { 273 cin >> n >> k; 274 275 for (int i = 0; i < n; i++) { 276 cin >> a[i]; 277 } 278 279 int lo = 1, hi = 1e9; 280 while (lo <= hi) { 281 int mid = lo + hi >> 1; 282 if (check(mid)) { 283 lo = mid + 1; 284 } else { 285 hi = mid - 1; 286 } 287 } 288 289 cout << hi << '\n'; 290 } 291 } 292 ``` 293 294 [1993E - Xor-Grid Problem](/contest/1993/problem/E "Codeforces Round 963 (Div. 2)") 295 296 **Hint 1** 297 298 Try applying an operation on the same row twice. Does it change the matrix significantly? 299 300 **Hint 2** 301 302 Now apply operations on two different rows. Does the second row (that the operation is applied) look familiar? 303 304 **Solution** 305 306 First, let's extend the original matrix by one unit in rows and columns (which means there's an additional $(n+1)$-th row and $(m+1)$-th column). Then, assign $a[i][m+1] = f(i)$ (xorsum of the $i$-th row) and $a[n+1][j] = g(j)$ (xorsum of the $j$-th column). That way, the operation is simplified as follows: 307 308 1. The first-type operation becomes swapping the $i$-th row with the $(n+1)$-th row. 309 2. The second-type operation becomes swapping the $j$-th column with the $(m+1)$-th column. 310 311 **Why?** 312 313 As we know, the first-type operation is to select any row $i$, then assign $a[i][j] = g(j)$ for all index $j$. But after the matrix extension, the value of $g(j)$ is also $a[n+1][j]$ so it means replacing the $i$-th row with the $(n+1)$-th one. 314 315 But we also need to care about the new value of $g(j)$ for future operations right? Surprisingly, the new value of $g(j)$ is nowhere strange, just the old value of element $a[i][j]$ being replaced right before! This takes advantage of the fact that if we perform the operation on the same row twice, the row become unchanged. After swapping two rows, the value of $a[n+1][j]$ then again become $g(j)$ of the new matrix. 316 317 The change of the second-type operation can be proven the same way. 318 319 That way, the matrix can be constructed by the permutation of rows, and the permutation of columns (as we can swap them however we want). After all operations, let's say the rows ordered from the top to the bottom are $r_1, r_2, \dots, r_{n+1}$. Similarly, the columns ordered from the left to the right are $c_1, c_2, \dots, c_{m+1}$. 320 321 Next thing to consider is: $\text{beauty(a)} = R + C$ — the beauty of the matrix, where: 322 323 * $R = \sum\limits_{i=1}^n \sum\limits_{j=2}^m \big|a[i][j] - a[i][j-1]\big|$ — sum of adjacent cells on the same row. 324 * $C = \sum\limits_{j=1}^m \sum\limits_{i=2}^n \big|a[i][j] - a[i-1][j]\big|$ — sum of adjacent cells on the same column. 325 326 Note that we include **neither** the $(n+1)$-th row **nor** the $(m+1)$-th column when calculating $R$ and $C$. That being said, after all operations, the $r_{n+1}$-th row and the $c_{m+1}$-th column is excluded and do not make any effect in further calculations anymore. 327 328 After that, we calculate two arrays: 329 330 * $dr[u][v] = $ sum of differences between $u$-th row and $v$-th row. 331 * $dc[u][v] = $ sum of differences between $u$-th column and $v$-th column. 332 333 Then, we'll rewrite the formulas of $R$ and $C$ as: $R = \sum\limits_{i=2}^n dr[r_{i-1}][r_i]$ and $C = \sum\limits_{i=2}^m dc[c_{i-1}][c_i]$. From now on, calculating $R$ and $C$ is as easy as solving the [Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem): finding a good permutation $r_1, \dots, r_n$ that produces the minimum $R$, and a good permutation $c_1, \dots, c_n$ that produces the minimum $C$. At the end, by summing $R + C$ we got the $\text{beauty}$ for a fixed excluded row and column for the matrix $a$. 334 335 Time complexity: $O((n+1)(m+1)^22^{m+1} + (m+1)(n+1)^22^{n+1})$, or just $O(n^32^n)$. 336 337 **Code (C++)** 338 339 ``` 340 #include <bits/stdc++.h> 341 using namespace std; 342 343 const int N = 16; 344 345 int n, m; 346 int a[N][N]; 347 348 int fr[N][N], fc[N][N]; 349 int w[N][N], dp[N][1<<N]; 350 351 int main() { 352 cin.tie(0)->sync_with_stdio(0); 353 354 int t; 355 cin >> t; 356 357 while (t--) { 358 cin >> n >> m; 359 360 for (int i = 0; i <= n; i++) a[i][m] = 0; 361 for (int j = 0; j <= m; j++) a[n][j] = 0; 362 363 for (int i = 0; i < n; i++) { 364 for (int j = 0; j < m; j++) { 365 cin >> a[i][j]; 366 a[i][m] ^= a[i][j]; 367 a[n][j] ^= a[i][j]; 368 a[n][m] ^= a[i][j]; 369 } 370 } 371 372 int fullmask_n = (1 << (n+1)) - 1; 373 int fullmask_m = (1 << (m+1)) - 1; 374 375 for (int rmv = 0; rmv <= m; rmv++) { 376 for (int i = 0; i <= n; i++) { 377 for (int j = i + 1; j <= n; j++) { 378 w[i][j] = 0; 379 for (int l = 0; l <= m; l++) { 380 if (rmv == l) continue; 381 w[i][j] += abs(a[i][l] - a[j][l]); 382 } 383 w[j][i] = w[i][j]; 384 } 385 } 386 387 for (int i = 0; i <= n; i++) { 388 fill(dp[i], dp[i] + fullmask_n, INT_MAX); 389 dp[i][1 << i] = 0; 390 } 391 392 for (int mask = 0; mask <= fullmask_n; mask++) { 393 for (int last = 0; last <= n; last++) { 394 if (~mask >> last & 1) continue; 395 if (__builtin_popcount(mask) == n) continue; 396 397 for (int next = 0; next <= n; next++) { 398 if (mask >> next & 1) continue; 399 400 int new_mask = mask | 1 << next; 401 dp[next][new_mask] = min( 402 dp[next][new_mask], 403 dp[last][mask] + w[last][next] 404 ); 405 } 406 } 407 } 408 409 for (int i = 0; i <= n; i++) { 410 fr[i][rmv] = INT_MAX; 411 int mask = fullmask_n ^ 1 << i; 412 413 for (int last = 0; last <= n; last++) { 414 fr[i][rmv] = min(fr[i][rmv], dp[last][mask]); 415 } 416 } 417 } 418 419 for (int rmv = 0; rmv <= n; rmv++) { 420 for (int i = 0; i <= m; i++) { 421 for (int j = i + 1; j <= m; j++) { 422 w[i][j] = 0; 423 for (int l = 0; l <= n; l++) { 424 if (rmv == l) continue; 425 w[i][j] += abs(a[l][i] - a[l][j]); 426 } 427 w[j][i] = w[i][j]; 428 } 429 } 430 431 for (int i = 0; i <= m; i++) { 432 fill(dp[i], dp[i] + fullmask_m, INT_MAX); 433 dp[i][1 << i] = 0; 434 } 435 436 for (int mask = 0; mask <= fullmask_m; mask++) { 437 for (int last = 0; last <= m; last++) { 438 if (~mask >> last & 1) continue; 439 if (__builtin_popcount(mask) == m) continue; 440 441 for (int next = 0; next <= m; next++) { 442 if (mask >> next & 1) continue; 443 444 int new_mask = mask | 1 << next; 445 dp[next][new_mask] = min( 446 dp[next][new_mask], 447 dp[last][mask] + w[last][next] 448 ); 449 } 450 } 451 } 452 453 for (int i = 0; i <= m; i++) { 454 fc[rmv][i] = INT_MAX; 455 int mask = fullmask_m ^ 1 << i; 456 457 for (int last = 0; last <= m; last++) { 458 fc[rmv][i] = min(fc[rmv][i], dp[last][mask]); 459 } 460 } 461 } 462 463 int ans = INT_MAX; 464 for (int i = 0; i <= n; i++) { 465 for (int j = 0; j <= m; j++) { 466 ans = min(ans, fr[i][j] + fc[i][j]); 467 } 468 } 469 470 cout << ans << '\n'; 471 } 472 } 473 ``` 474 475 [1993F1 - Dyn-scripted Robot (Easy Version)](/contest/1993/problem/F1 "Codeforces Round 963 (Div. 2)") 476 477 **Hint 1** 478 479 Let the robot moves freely (no modification on the script). 480 481 **Hint 2** 482 483 The new path of the robot is the "mirrored" version of how the robot must go. 484 485 **General idea** 486 487 Imagine we have two robots, let's call them Alex and Bob. Alex is the one who follows the instruction well, but Bob doesn't (if he tries to move outside the box, he keeps going without modifying the script). Then, you follow the path of each robot that is moving. How do you think their paths differ from each other? 488 489 Yes! Suppose at some moment they reach the top side of the box at the same time. Suddenly, Bob wants to move up while Alex know the discipline and modify the script before executing the command and move down. Then, each of them is $1$ unit away from the top side of the box. If Bob keeps moving up, Alex keep moving down. In case Bob changes his mind and move down then this time Alex changes her mind and move up. 490 491 What do we learn from this? They move like two objects facing each other through a mirror. Actually there are four mirror of them, placing at the four sides of the box. 492 493 Now, let's say Bob moves up so much that Alex follows the script and reaches the top side and the bottom side as well. Because of that, she has to change the script once again and start moving up like Bob. 494 495 When Alex reaches the bottom side at point $(x, 0)$, then Bob should be at point $(x, 2H)$ (prove it yourself!). If Bob keeps moving up to the point $(x, 4H), (x, 6H), or (x, 8H), \dots$, at these moment Alex will also be at point $(x, 0)$. That being said, Alex's position is $(x, 0)$ then Bob's position must be $(x, y)$ where y is a multiple of $2H$. 496 497 This idea is exactly the same as if Bob were moving sideways (left or right). As we only care about the number of times Alex's position is $(0, 0)$, we know that if we don't change the script at all, the position of the robot must be $(x, y)$ where $x$ is a multiple of $2W$, and $y$ is a multiple of $2H$. 498 499 **Solution** 500 501 So apparently, we need to calculate the number of times the robot reaches $(x, y)$, where $x$ is a multiple of $2W$ and $y$ is a multiple of $2H$ (see the general idea above). 502 503 Let's call $t_k = (x_k, y_k)$ how much the robot moves (in direction) after executing the first $k$ commands of the script. Then: $t_0 = (0, 0)$ and $t_k$ can be calculated through $t_{k-1}$ and $s_k$. 504 505 The robot will execute the script $k$ times and the script contains $n$ commands, so we have $nk$ positions to check out. Each position can be represented by: $(x, y) = it_n + t_j = (ix_n + x_j, iy_n + y_j)$ (where $0\le i\le k-1$ and $1\le j\le n$). Besides, we need: 506 507 * $x\equiv 0\pmod{2W} \Longrightarrow ix_n + x_j\equiv 0\pmod{2W} \Longrightarrow x_j\equiv -ix_n\pmod{2W}$ 508 * $y\equiv 0\pmod{2H} \Longrightarrow iy_n + y_j\equiv 0\pmod{2H} \Longrightarrow y_j\equiv -iy_n\pmod{2H}$ 509 510 Lastly, we can traverse all possible $i$ from $0$ to $k-1$ and count the number of $j$ that satisfies the above equivalence. One possible way to do this is to use a map to count each element in the array $t_1, t_2, \dots, t_n$. Summing all the counts will give the answer for this problem. 511 512 Time complexity: $O((n + k)\log n)$ 513 514 **Code (C++)** 515 516 ``` 517 #include <bits/stdc++.h> 518 using namespace std; 519 520 using ll = long long; 521 const int N = 1e6 + 5; 522 523 string s; 524 ll n, k, w, h; 525 ll tx[2*N], ty[2*N]; 526 map<pair<ll, ll>, ll> cnt; 527 528 int main() { 529 cin.tie(0)->sync_with_stdio(0); 530 531 int t; 532 cin >> t; 533 534 while (t--) { 535 cin >> n >> k >> w >> h >> s; 536 537 cnt.clear(); 538 ll x = 0, y = 0; 539 540 for (int i = 0; i < n; i++) { 541 if (s[i] == 'L') x--; 542 if (s[i] == 'R') x++; 543 if (s[i] == 'D') y--; 544 if (s[i] == 'U') y++; 545 546 x = (x + 2*w) % (2*w); 547 y = (y + 2*h) % (2*h); 548 cnt[{x, y}]++; 549 } 550 551 ll ans = 0; 552 for (int i = 0; i < k; i++) { 553 ll vx = (-i*x%(2*w) + 2*w)%(2*w); 554 ll vy = (-i*y%(2*h) + 2*h)%(2*h); 555 ans += cnt[{vx, vy}]; 556 } 557 558 cout << ans << '\n'; 559 } 560 } 561 ``` 562 563 [1993F2 - Dyn-scripted Robot (Hard Version)](/contest/1993/problem/F2 "Codeforces Round 963 (Div. 2)") 564 565 **Solution** 566 567 The idea of this version is almost the same as F1: counting the number of pairs $(i, j)$ that satisfies: 568 569 * $ix_n + x_j\equiv 0\pmod{2W}$, and 570 * $iy_n + y_j\equiv 0\pmod{2H}$ 571 572 However, as $k$ is increased to $10^{12}$ we cannot brute-force the same way as the previous version. Luckily, there is a more efficient way. We need to modify these equivalences a bit: 573 574 * $ix_n \equiv -x_j\pmod{2W}$ $(*)$ 575 * $iy_n \equiv -y_j\pmod{2H}$ 576 577 As we can see, these two equivalences have the same format $ia \equiv b\pmod{M}$. To solve this equivalence for $i$, one way to hang around is to divide $a$, $b$ and $M$ by $\gcd(a, M)$. If $b$ is not divisible, there is no solution! Otherwise, we come up with: 578 579 $i \equiv ba^{-1}\pmod{M}$ 580 581 Where $a^{-1}$ is the [modular inverse](https://cp-algorithms.com/algebra/module-inverse.html) of $a$. We can always calculate it because the condition $\gcd(a, M)=1$ is satisfied. 582 583 Let's define $g=\gcd(2W, x_n)$, $c_x = -\frac{x_j}g\left(\frac{x_n}g\right)^{-1}$ and $W'=\frac{2W}{g}$ (similar for $c_y$ and $H'$). Then, the solutions of the equivalences at $(*)$ are: 584 585 * $i\equiv c_x\pmod{W'}$ 586 * $i\equiv c_y\pmod{H'}$ 587 588 This system of equivalences can be solved using [Chinese Remainder Theorem](https://codeforces.com/blog/entry/61290). After some calculations, we come up with: 589 590 * $i=c_x + zW'$ ($z$ is a non-negative integer). 591 * $zW'\equiv c_y-c_x\pmod{H'}$ $(**)$ 592 593 $(**)$ can be solved for $z$ the same way as $(*)$. Now we know the solution is $i \equiv c_x + zW' \pmod{lcm(W', H')}$, the last thing to do is to count number of such value doesn't exceed $k-1$ and we're done! 594 595 Time complexity: $O(Nlog(W))$ 596 597 **Code (C++)** 598 599 ``` 600 #include <bits/stdc++.h> 601 using namespace std; 602 603 using ll = long long; 604 605 namespace CRT { 606 // v * inv(v, M) = 1 (mod M) 607 ll inv(ll v, ll M) { 608 ll a = 1, b = 0; 609 for (ll x = v, y = M; x != 0; ) { 610 swap(a, b -= y/x * a); 611 swap(x, y -= y/x * x); 612 } 613 return b + (b<0) * M; 614 } 615 616 // Minimum x that ax = b (mod c) 617 ll solve_1(ll a, ll b, ll c) { 618 ll g = gcd(a, c); 619 if (b % g != 0) return -1; 620 return b/g * inv(a/g, c/g) % (c/g); 621 } 622 623 // Minimum x that x%b = a and x%d = c 624 ll solve_2(ll a, ll b, ll c, ll d) { 625 ll t = (c-a)%d; 626 if (t < 0) t += d; 627 ll k = solve_1(b, t, d); 628 return k==-1 ? -1 : a + k*b; 629 } 630 } 631 632 const int N = 1e6 + 5; 633 634 ll n, k, w, h; 635 ll x[N], y[N]; 636 637 int main() { 638 cin.tie(nullptr) -> sync_with_stdio(false); 639 640 int tc; cin >> tc; 641 while (tc--) { 642 string s; 643 cin >> n >> k >> w >> h >> s; 644 645 for (int i = 1; i <= n; i++) { 646 x[i] = x[i-1] + (s[i-1] == 'R') - (s[i-1] == 'L'); 647 y[i] = y[i-1] + (s[i-1] == 'U') - (s[i-1] == 'D'); 648 x[i] += (x[i] < 0) * 2*w - (x[i] >= 2*w) * 2*w; 649 y[i] += (y[i] < 0) * 2*h - (y[i] >= 2*h) * 2*h; 650 } 651 652 ll ww = 2*w / gcd(x[n], 2*w); 653 ll hh = 2*h / gcd(y[n], 2*h); 654 ll ans = 0, l = lcm(ww, hh); 655 656 for (int i = 1; i <= n; i++) { 657 ll cx = CRT::solve_1(x[n], 2*w - x[i], 2*w); 658 ll cy = CRT::solve_1(y[n], 2*h - y[i], 2*h); 659 if (cx == -1 || cy == -1) continue; 660 661 ll result = CRT::solve_2(cx, ww, cy, hh); 662 if (result != -1 && result < k) { 663 ans += (k - result - 1) / l + 1; 664 } 665 } 666 667 cout << ans << '\n'; 668 } 669 } 670 ```