codeforces-scrape

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

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 ![ ](/predownloaded/8f/81/8f813ba116db267c0fb62069794fa8f46cf7b970.png)
     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 ```