codeforces-scrape

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

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 ```