2056.md (20458B)
1 Source: https://codeforces.com/blog/entry/138487 2 3 **Rating predictions** 4 5 | | A | B | C | D | E | F1 | F2 | 6 | --- | --- | --- | --- | --- | --- | --- | --- | 7 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 1200 | 1400 | 2000 | 2200 | 2700 | 2800 | 8 | [Intellegent](/profile/Intellegent "Master Intellegent") | 800 | 1200 | 1600 | 2000 | 2300 | | | 9 | [mwen](/profile/mwen "Master mwen") | 800 | 1200 | 1300 | 1800 | 2300 | | | 10 | [Markadiusz](/profile/Markadiusz "Grandmaster Markadiusz") | 800 | 1100 | 1300 | 1800 | 2300 | 2500 | 2800 | 11 | [_istil](/profile/_istil "International Grandmaster _istil") | 800 | | [1600, 2000] | 2000 | | 2400 | 2700 | 12 | [flammifer](/profile/flammifer "Master flammifer") | 1000 | 1200 | 1500 | 2000 | 2100 | | | 13 | [iLoveIOI](/profile/iLoveIOI "Master iLoveIOI") | 800 | 1100 | 1600 | 2000 | 2400 | | | 14 | [A_G](/profile/A_G "Legendary Grandmaster A_G") | 800 | 1100 | 1500 | 1700 | 2100 | 2600 | 2700 | 15 | [DilshodbekX](/profile/DilshodbekX "Master DilshodbekX") | 800 | 1200 | 1500 | 1800 | 2200 | | | 16 17 | | A | B | C | D | E | F1 | F2 | 18 | --- | --- | --- | --- | --- | --- | --- | --- | 19 | Average | 822 | 1163 | 1500 | 1900 | 2238 | 2550 | 2750 | 20 | Actual | 800 | 1300 | 1200 | 2200 | 2500 | 2700 | 3000 | 21 22 [2056A - Shape Perimeter](/contest/2056/problem/A "Codeforces Round 997 (Div. 2)") 23 24 **Hints** 25 26 **Hint 1** 27 28 Look at the picture. I mean, **look** at the picture. 29 30 **Hint 2** 31 32 Consider coordinates $x$ and $y$ separately. 33 34 **Solution** 35 36 Consider coordinates $x$ and $y$ separately. Since $1 \le x_i, y_i \le m - 1$, after each step both coordinates increase and remain connected with the previous square. 37 38 From the picture we can see that each coordinate spans from the bottom-left corner of the first square to the top-right corner of the last square. 39 40 To calculate the perimeter we can add the length of that interval for both coordinates and multiply it by $2$, as it is counted in the perimeter twice, going in both directions: 41 42  43 44 The coordinates of the bottom-left corner of the first square are $(x_1, y_1)$ and of the top-right corner of the last square are $(m + \sum\limits_{i = 1}^n x_i, m + \sum\limits_{i = 1}^n y_i)$. 45 46 The lengths of the intervals are $m + \sum\limits_{i = 2}^n x_i$ and $m + \sum\limits_{i = 2}^n y_i$. 47 48 Therefore, the answer is $2(2m + \sum\limits_{i = 2}^n (x_i + y_i))$. 49 50 **Code** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 void solve() { 58 int n, m; 59 cin >> n >> m; 60 vector<int> x(n), y(n); 61 for(int i = 0; i < n; i++) { 62 cin >> x[i] >> y[i]; 63 } 64 int ans = 2 * (accumulate(x.begin(), x.end(), 0) + m - x[0] + accumulate(y.begin(), y.end(), 0) + m - y[0]); 65 cout << ans << '\n'; 66 } 67 68 signed main() { 69 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 70 int ttt = 1; 71 cin >> ttt; 72 while(ttt--) { 73 solve(); 74 } 75 } 76 ``` 77 78 [2056B - Find the Permutation](/contest/2056/problem/B "Codeforces Round 997 (Div. 2)") 79 80 **Hints** 81 82 **Hint 1** 83 84 "It can be proven that permutation $p$ can be uniquely determined" 85 86 **Hint 2** 87 88 This means that there is an order of elements. How to determine whether $x$ should be earlier in that order than $y$? 89 90 **Solution** 91 92 Consider two elements $x \lt y$. Suppose their positions in $p$ are $i$ and $j$ correspondigly. 93 94 How can we determine if $i \lt j$? If $i \lt j$ and $x \lt y$, we will have $g_{x, y} = g_{y, x} = 1$. Otherwise, $i \gt j$ and $x \lt y$, so $g_{x, y} = g_{y, x} = 0$. 95 96 So if $g_{x, y} = 1$, we know that $i \lt j$, otherwise $i \gt j$. 97 98 That way we can determine for each pair of elements which one of them should appear earlier in the permutation. Notice that this is just a definition of a comparator, which proves that the permutation is indeed unique. We can find it by sorting $p = [1, 2, \ldots, n]$ with that comparator. 99 100 **Code** 101 102 ``` 103 #include <bits/stdc++.h> 104 105 using namespace std; 106 107 void solve() { 108 int n; 109 cin >> n; 110 vector<string> g(n); 111 for(auto &i : g) { 112 cin >> i; 113 } 114 vector<int> p(n); 115 iota(p.begin(), p.end(), 0); 116 sort(p.begin(), p.end(), 117 [&](int x, int y) { 118 if(g[x][y] == '1') return x < y; 119 else return x > y; 120 }); 121 for(auto i : p) cout << i + 1 << " "; cout << '\n'; 122 } 123 124 signed main() { 125 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 126 int ttt = 1; 127 cin >> ttt; 128 while(ttt--) { 129 solve(); 130 } 131 } 132 ``` 133 134 [2056C - Palindromic Subsequences](/contest/2056/problem/C "Codeforces Round 997 (Div. 2)") 135 136 **Hints** 137 138 **Hint 1** 139 140 Analyze the example with $n = 6$. 141 142 **Hint 2** 143 144 If $[a_1, a_2, \ldots, a_k, a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n]$ is a palindrome, then $[a_1, a_2, \ldots, a_k, a_i, a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n]$ is also a palindrome for all $k \lt i \lt n - k + 1$. 145 146 **Solution** 147 148 If $[a_1, a_2, \ldots, a_k, a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n]$ is a palindrome, then $[a_1, a_2, \ldots, a_k, a_i, a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n]$ is also a palindrome for all $k \lt i \lt n - k + 1$, because we make it's length odd and add $a_i$ to the middle. 149 150 We can use this to create a sequence with a big value of $g$. However, we shouldn't create a palindrome of a greater length than $2k + 1$ by using the fact above. 151 152 That make us try something like $a = [1, 2, 3, \ldots, n - 2, 1, 2]$. $f(a) = 3$ here, and any of $[a_1, a_i, a_{n - 1}]$ for $1 \lt i \lt n - 1$ and $[a_2, a_i, a_n]$ for $2 \lt i \lt n$ are palindromes, which means that $g(a) = 2(n - 3) = 2n - 6$. 153 154 This construction works for $n \ge 7$, so we have to handle $n = 6$ separately. 155 156 We can also use the construction from the example with $n = 6$ directly: $a = [1, 1, 2, 3, 4, \ldots, n - 3, 1, 2]$, which has $g(a) = 3n - 11$. 157 158 **Code** 159 160 ``` 161 #include <bits/stdc++.h> 162 163 using namespace std; 164 165 void solve() { 166 int n; 167 cin >> n; 168 if (n == 6) { 169 cout << "1 1 2 3 1 2\n"; 170 } 171 else if(n == 9) { 172 cout << "7 3 3 7 5 3 7 7 3\n"; 173 } 174 else if(n == 15) { 175 cout << "15 8 8 8 15 5 8 1 15 5 8 15 15 15 8\n"; 176 } 177 else { 178 for(int i = 1; i <= n - 2; i++) cout << i << " "; cout << "1 2\n"; 179 } 180 } 181 182 signed main() { 183 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 184 int ttt = 1; 185 cin >> ttt; 186 while(ttt--) { 187 solve(); 188 } 189 } 190 ``` 191 192 [2056D - Unique Median](/contest/2056/problem/D "Codeforces Round 997 (Div. 2)") 193 194 **Hints** 195 196 **Hint 1** 197 198 Solve the problem when $a_i \le 2$. 199 200 **Hint 2** 201 202 Assign $b_i = 1$ if $a_i = 2$ and $b_i = -1$ if $a_i = 1$ and calculate the number of bad subarrays. 203 204 **Hint 3** 205 206 Extend this solution for $a_i \le 10$, however, you need to take overcounting into account. 207 208 **Solution** 209 210 When is a subarray $a[l, r]$ not good? 211 212 If $r - l + 1$ is odd, $a[l, r]$ can't be bad. Otherwise, suppose the median of $a[l, r]$ is $x$. Then there need to be exactly $\frac{r - l + 1}{2}$ elements in $a[l, r]$ that are $\le x$ and exactly $\frac{r - l + 1}{2}$ that are $ \gt x$. 213 214 This gives us an idea to calculate the number of bad subarrays with a median of $x$. 215 216 Create another array $b$ of size $n$, where $b_i = -1$ if $a_i \le x$ and $b_i = 1$ otherwise. 217 218 $a[l, r]$, which has a median of $x$, is bad if and only if $\sum\limits_{i = l}^r b_i = 0$ and $r - l + 1$ is even. 219 220 Notice that the second condition is not needed, as the sum of an odd length subarray of $b$ is always odd, so it can't be zero. 221 222 Therefore, $a[l, r]$ with a median of $x$ is bad iff $\sum\limits_{i = l}^r b_i = 0$. 223 224 If there is no $x$ in $[l, r]$, then the median of $a[l, r]$ trivially can't be equal to $x$. 225 226 If there is an occurrence of $x$ in $a[l, r]$ and $\sum\limits_{i = l}^r b_i = 0$, notice that the median of $a[l, r]$ will always be exactly $x$. This is true because $\frac{r - l + 1}{2}$ smallest elements of $a[l, r]$ are all $\le x$, and there is an occurrence of $x$, so $\frac{r - l + 1}{2}$-th smallest element must be $x$. 227 228 This allows us to simply count the number of subarrays of $b$ with a sum of $0$ and with an occurrence of $x$ to count the number of bad subarrays with median $x$. 229 230 We can subtract that value from $\frac{n(n + 1)}{2}$ for all $x$ between $1$ and $A = 10$ to solve the problem in $O(nA)$. 231 232 **Code** 233 234 ``` 235 #include <bits/stdc++.h> 236 237 using namespace std; 238 239 const int MAX = 11; 240 241 int main() { 242 int tests; 243 cin >> tests; 244 for(int test = 0; test < tests; test++) { 245 int n; 246 cin >> n; 247 vector<int> a(n); 248 for(auto &i : a) { 249 cin >> i; 250 } 251 long long ans = 0; 252 for(int x = 1; x < MAX; x++) { 253 vector<int> b(n); 254 for(int i = 0; i < n; i++) { 255 b[i] = (a[i] > x? 1 : -1); 256 } 257 int sum = n; 258 vector<int> pref(n); 259 for(int i = 0; i < n; i++) { 260 pref[i] = sum; 261 sum += b[i]; 262 } 263 vector<int> cnt(2 * n + 1); 264 sum = n; 265 int j = 0; 266 for(int i = 0; i < n; i++) { 267 if(a[i] == x) { 268 while(j <= i) { 269 cnt[pref[j]]++; 270 j++; 271 } 272 } 273 sum += b[i]; 274 ans += cnt[sum]; 275 } 276 } 277 ans = 1ll * n * (n + 1) / 2 - ans; 278 cout << ans << '\n'; 279 } 280 return 0; 281 } 282 ``` 283 284 [2056E - Nested Segments](/contest/2056/problem/E "Codeforces Round 997 (Div. 2)") 285 286 **Hints** 287 288 **Hint 1** 289 290 Forget about counting. What is the maximum size of $T$ if $m = 0$? 291 292 **Hint 2** 293 294 It is $2n - 1$. What if $m$ isn't $0$? 295 296 **Hint 3** 297 298 It is still $2n - 1$. To prove this represent a *good* set as a forest. 299 300 **Hint 4** 301 302 We can always add $[1, n]$ and $[i, i]$ for all $1 \le i \le n$ to $S$. Now the tree of $S$ has exactly $n$ leaves. What if a vertex has more than $2$ children? 303 304 **Hint 5** 305 306 What is the number of solutions when $m = 0$? 307 308 **Hint 6** 309 310 It is the number of full binary trees with $n$ leaves, which is $C_{n - 1}$, where $C$ denotes the Catalan's sequence. Extend this idea to count the number of solutions for a general tree of $S$. 311 312 **Solution** 313 314 Any *good* set has a tree-like structure. 315 316 Specifically, represent $S$ as a forest the following way: segment $[l, r]$ has a parent $[L, R]$ iff $[l, r] \in [L, R]$ and $R - L + 1$ is minimized (its parent is the shortest interval in which it lies). This segment is unique (or does not exist), because there can't be two segments with minimum length that cover $[l, r]$, as they would partially intersect otherwise. 317 318 Notice that we can always add $[1, n]$ and $[i, i]$ for all $1 \le i \le n$ if they aren't in $S$ yet. Now the forest of $S$ is a tree with exactly $n$ leaves. 319 320 Suppose $[L, R]$ has $k$ children $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$. If $k \gt 2$, we can always add $[l_1, r_2]$ to $S$, which decreases the number of children of $[L, R]$ by $1$ and increases the size of $S$ by $1$. 321 322 Therefore, in the optimal solution each segment has at most $2$ children. Having exactly one child is impossible, as we have added all $[i, i]$, so every index of $[L, R]$ is covered by its children. 323 324 This means that we have a tree where each vertex has either $0$ or $2$ children, which is a full binary tree. 325 326 We have $n$ leaves, and every full binary tree with $n$ leaves has exactly $2n - 1$ vertices, so this is always the optimal size of $T$ regardless of $S$. 327 328 To count the number of $T$, notice that when $m = 0$ the answer is the number of full binary trees with $n$ leaves, which is $C_{n - 1}$, where $C$ denotes the Catalan's sequence. 329 330 To extend this to a general tree, we can add $[1, n]$ and $[i, i]$ for all $1 \le i \le n$ to $S$. 331 332 Now suppose $[L, R]$ has $k \ge 2$ children $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$. We need to merge some children. We can treat $[l_1, r_1]$ as $[1, 1]$, $[l_2, r_2]$ as $[2, 2]$, etc. This is now the same case as $m = 0$, so there are $C_{k - 1}$ ways to merge children of $[L, R]$. 333 334 Each vertex is independent of each other, so the answer is $\prod C_{c_v - 1}$ over all non-leaves $v$, where $c_v$ is the number of children of $v$. 335 336 We can construct the tree in $O(n \log n)$ by definition or in $O(n)$ using a stack. 337 338 **Code** 339 340 ``` 341 #include <bits/stdc++.h> 342 343 using namespace std; 344 345 const int mod = 998244353; 346 const int MAX = 4e5 + 42; 347 348 int fact[MAX], inv[MAX], inv_fact[MAX]; 349 350 int C(int n, int k) { 351 if(n < k || k < 0) return 0; 352 return (long long) fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod; 353 } 354 355 int Cat(int n) { 356 return (long long) C(2 * n, n) * inv[n + 1] % mod; 357 } 358 359 int binpow(int x, int n) { 360 int ans = 1; 361 while(n) { 362 if(n & 1) ans = (long long) ans * x % mod; 363 n >>= 1; 364 x = (long long) x * x % mod; 365 } 366 return ans; 367 } 368 369 void solve() { 370 int n, m; 371 cin >> n >> m; 372 int initial_m = m; 373 vector<pair<int, int>> a(m); 374 for(auto &[l, r] : a) { 375 cin >> l >> r; 376 } 377 bool was_full = 0; 378 vector<int> was_single(n + 1); 379 for(auto [l, r] : a) was_full |= (r - l + 1 == n); 380 for(auto [l, r] : a) { 381 if(l == r) was_single[l] = 1; 382 } 383 if(!was_full) { 384 a.push_back({1, n}); 385 m++; 386 } 387 for(int i = 1; i <= n; i++) { 388 if(!was_single[i] && n != 1) { 389 a.push_back({i, i}); 390 m++; 391 } 392 } 393 for(auto &[l, r] : a) r = -r; 394 sort(a.begin(), a.end()); 395 vector<int> deg(m); 396 for(int i = 0; i < m; i++) { 397 int j = i + 1; 398 while(j < m) { 399 if(-a[i].second < a[j].first) break; 400 deg[i]++; 401 j = upper_bound(a.begin(), a.end(), make_pair(-a[j].second, 1)) - a.begin(); 402 } 403 } 404 for(auto &[l, r] : a) r = -r; 405 int ans = 1; 406 for(int i = 0; i < m; i++) { 407 if(deg[i] > 0) { 408 assert(deg[i] >= 2); 409 ans = (long long) ans * Cat(deg[i] - 1) % mod; 410 } 411 } 412 cout << ans << '\n'; 413 } 414 415 signed main() { 416 fact[0] = 1; 417 for(int i = 1; i < MAX; i++) fact[i] = (long long) fact[i - 1] * i % mod; 418 inv_fact[MAX - 1] = binpow(fact[MAX - 1], mod - 2); 419 for(int i = MAX - 1; i; i--) inv_fact[i - 1] = (long long) inv_fact[i] * i % mod; 420 assert(inv_fact[0] == 1); 421 for(int i = 1; i < MAX; i++) inv[i] = (long long) inv_fact[i] * fact[i - 1] % mod; 422 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 423 int ttt = 1; 424 cin >> ttt; 425 while(ttt--) { 426 solve(); 427 } 428 } 429 ``` 430 431 [2056F1 - Xor of Median (Easy Version)](/contest/2056/problem/F1 "Codeforces Round 997 (Div. 2)"), [2056F2 - Xor of Median (Hard Version)](/contest/2056/problem/F2 "Codeforces Round 997 (Div. 2)") 432 433 **Hints** 434 435 **Hint 1** 436 437 The order of the sequence doesn't matter. What if we fix the sequence $\text{cnt}$ and then calculate its contribution to the answer? 438 439 **Hint 2** 440 441 By Lucas's theorem the contribution is odd iff for each set bit in $n$ there is exactly one $i$ such that $\text{cnt}_i$ has this bit set, and $\sum\limits_{i = 0}^{m - 1} \text{cnt}_i = n$. In other words, $\text{cnt}$ has to partition all set bits in $n$. For a fixed $\text{cnt}$ with an odd contribution, what will be the median? 442 443 **Hint 3** 444 445 There is a very big element in $\text{cnt}$. 446 447 **Hint 4** 448 449 Since $\text{cnt}$ partitions the bits of $n$, there will be $i$ which has it's most significant bit. This means that $2\text{cnt}_i \gt n$, so $i$ will always be the median. 450 451 **Hint 5** 452 453 Suppose there are $p$ non-zero elements in $\text{cnt}$. We can partition all set bits of $n$ into $p$ non-empty subsequences and then choose which of the $m$ numbers will occur. How can we calculate the answer now? 454 455 **Hint 6** 456 457 The only time we use the value of $n$ is when we partition all of it's set bits into subsequences. That means that the answer only depends on the number of set bits in $n$, not on $n$ itself. This allows us to solve the easy version by fixing the value of $p$ and the value of the median. 458 459 **Hint 7** 460 461 To solve the hard version use Lucas's theorem again and do digit dp or SOS-dp. 462 463 **Solution** 464 465 The order of the sequence doesn't matter, so let's fix the sequence $\text{cnt}$ and calculate its contribution to the answer. 466 467 For a fixed $\text{cnt}$, the number of ways to order $a$ is $\binom{n}{\text{cnt}_0, \text{cnt}_1, \ldots, \text{cnt}_{m - 1}}$. By Lucas's theorem the contribution is odd iff for each set bit in $n$ there is exactly one $i$ such that $\text{cnt}_i$ has this bit set, and $\sum\limits_{i = 0}^{m - 1} \text{cnt}_i = n$. In other words, $\text{cnt}$ has to partition all set bits in $n$. 468 469 Since $\text{cnt}$ partitions the bits of $n$, there will be $i$ which has it's most significant bit. This means that $2\text{cnt}_i \gt n$, so $i$ will always be the median. 470 471 Suppose there are $p$ non-zero elements in $\text{cnt}$. We can partition all set bits of $n$ into $p$ non-empty subsequences and then choose which of the $m$ numbers will occur. 472 473 The only time we use the value of $n$ is when we partition all of it's set bits into subsequences. That means that the answer only depends on the number of set bits in $n$, not on $n$ itself. 474 475 So let's fix $p$ as the number of non-zero elements in $\text{cnt}$ and $x$ as the median. Denote $b$ as the number of set bits in $n$. There are $S(b, p)$ ways to partition the bits into $p$ non-empty subsequences, where $S$ denotes Stirling number of the second kind. There are $\binom{x}{p - 1}$ ways to choose which other elements will have non-zero $\text{cnt}$, because the median will always have the largest value and non-zero $\text{cnt}_i$ must be non-decreasing. 476 477 The answer is then $\oplus_{p = 1}^b \oplus_{x = 0}^{m - 1} \left(S(b, p) \bmod 2\right) \cdot \left(\binom{x}{p - 1} \bmod 2\right) \cdot x$, which we can calculate in $O(km)$, which solves the easy version. 478 479 To solve the hard version we can use Lucas's theorem again to get that the contribution of $x$ to the answer is the XOR of $S(b, p + 1) \bmod 2$ over all submasks $p$ of $x$. We can limit $p$ to be between $0$ and $b - 1$. 480 481 That means that only $L = \lceil \log_2 b \rceil$ last bits of $x$ determine whether $x$ contributes something to the answer. We can find which of $2^L$ of them will have an odd contribution by setting $dp_p = S(b, p + 1) \bmod 2$, and calculating it's SOS-dp. Then for fixed $L$ last bits it is easy to find the XOR of all $x \lt m$ with those bits. 482 483 Note that $S(n, k)$ is odd iff $(n - k) \text{&} \frac{k - 1}{2} = 0$, which we can derive from the recurrence, combinatorics, google or OEIS. 484 485 This solves the problem in $O(b \log b) = O(k \log k)$. 486 487 **F1 code** 488 489 ``` 490 #include <bits/stdc++.h> 491 492 using namespace std; 493 494 int C(int n, int k) { 495 return (n & k) == k; 496 } 497 498 int S(int n, int k) { 499 return !(n - k & (k - 1 >> 1)); 500 } 501 502 int brute_partition(int n, int m) { 503 vector<int> cnt; 504 int ans = 0; 505 for(int k = 1; k <= n; k++) { 506 if(!S(n, k)) continue; 507 for(int median = 1; median < m; median++) { 508 if(C(median, k - 1)) ans ^= median; 509 } 510 } 511 return ans; 512 } 513 514 void solve() { 515 int k, m; 516 string s; 517 cin >> k >> m >> s; 518 int n = 0; 519 for(auto &i : s) n += i & 1; 520 int ans = brute_partition(n, m); 521 cout << ans << '\n'; 522 } 523 524 signed main() { 525 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 526 int ttt = 1; 527 cin >> ttt; 528 while(ttt--) { 529 solve(); 530 } 531 } 532 ``` 533 534 **F2 code** 535 536 ``` 537 #include <bits/stdc++.h> 538 539 using namespace std; 540 541 int S(int n, int k) { 542 return !(n - k & (k - 1 >> 1)); 543 } 544 545 int get(int n, int m) { 546 int L = __lg(n) + 1; 547 int up = 1 << L; 548 vector<int> dp(up); 549 for(int i = 0; i < n; i++) dp[i] = S(n, i + 1); 550 for(int j = 0; j < L; j++) { 551 for(int i = 0; i < up; i++) { 552 if(i >> j & 1) dp[i] ^= dp[i ^ (1 << j)]; 553 } 554 } 555 int ans = 0; 556 for(int lst = 0; lst < up && lst < m; lst++) { 557 if(!dp[lst]) continue; 558 int cnt = m - 1 - lst >> L; 559 if(cnt & 1 ^ 1) ans ^= lst; 560 if(cnt % 4 == 0) ans ^= cnt << L; 561 else if(cnt % 4 == 1) ans ^= 1ll << L; 562 else if(cnt % 4 == 2) ans ^= cnt + 1 << L; 563 else ans ^= 0; 564 } 565 return ans; 566 } 567 568 void solve() { 569 int k, m; 570 string s; 571 cin >> k >> m >> s; 572 int n = 0; 573 for(auto &i : s) n += i & 1; 574 int ans = get(n, m); 575 cout << ans << '\n'; 576 } 577 578 signed main() { 579 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 580 int ttt = 1; 581 cin >> ttt; 582 while(ttt--) { 583 solve(); 584 } 585 } 586 ```