codeforces-scrape

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

1734.md (23250B)


      1 Source: https://codeforces.com/blog/entry/107231
      2 
      3 Thank you for your participation!
      4 
      5 ## [1734A — Select Three Sticks](https://codeforces.com/contest/1734/problem/A)
      6 
      7 We first sort the array $a$ in non-decreasing order.
      8 
      9 Denote the indices of the elements that we choose from $a$ to be $x$, $y$, and $z$, where $1 \le x \lt y \lt z \le n$, and the final value (after performing the operations) of the concerned elements to be $v$.
     10 
     11 The minimum required number of operations is then $|a_x-v|+|a_y-v|+|a_z-v|$. It is well-known that such expression attains its minimum value when $v$ is the median of $a_x$, $a_y$, and $a_z$. Since the array $a$ has already been sorted, it is best to assign $v$ to be $a_y$.
     12 
     13 Our expression then becomes $|a_x-a_y|+|a_y-a_y|+|a_z-a_y|=(a_y-a_x)+0+(a_z-a_y)=a_z-a_x$. We would like to minimize the value of $a_z$, which implies $z$ should be as small as possible since $a$ is sorted. It is clear that taking $z=y+1$ would minimize the value of the expression. Similarly, we can show that we can take $x=y-1$ to minimize the value of the expression.
     14 
     15 Therefore, the only possible values of the triplets $(x,y,z)$ are of the form $(t,t+1,t+2)$ for positive integers $1 \le t \le n-2$, and we can iterate through all such triplets and find the best one.
     16 
     17 The time complexity is $\Theta(n \log n)$ per case due to sorting.
     18 
     19 **Code in C++**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 using namespace std;
     24 void solve(){
     25 	int n;
     26 	cin>>n;
     27 	int a[n+1];
     28 	for (int i=1; i<=n; i++){
     29 		cin>>a[i];
     30 	}
     31 	sort(a+1,a+n+1);
     32 	int ans=2e9;
     33 	for (int i=3; i<=n; i++){
     34 		ans=min(ans,a[i]-a[i-2]);
     35 	}
     36 	cout<<ans<<'\n';
     37 }
     38 int main(){
     39 	int t;
     40 	cin>>t;
     41 	for (int i=1; i<=t; i++){
     42 		solve();
     43 	}
     44 }
     45 ```
     46 
     47 ## [1734B — Bright, Nice, Brilliant](https://codeforces.com/contest/1734/problem/B)
     48 
     49 Note that the brightnesses of the rooms on the $i$-th floor is at most $i$. This is because in room $(i,1)$, only $i$ rooms, namely, $(1,1)$, $(2,1)$, $\ldots$, $(i,1)$ can reach to $(i,1)$ through some number of staircases.
     50 
     51 It is also possible to find a configuration of torches in the pyramid such that the brightnesses of the rooms on the $i$-th floor is exactly $i$, i.e. it attains the upper bound.
     52 
     53 The configuration is as follows: Room $(i,j)$ contains a torch if and only if it is the leftmost room ($i=1$) or the rightmost room ($i=j$) on the $i$-th floor.
     54 
     55 This is valid because for all rooms $(i,j)$, it can be reached from $(1,1)$, $(2,1)$, $(3,1)$, $\ldots$, $(i-j+1,1)$ and $(2,2)$, $(3,3)$, $\ldots$, $(j,j)$. In other words, room $(i,j)$ has brightness $(i-j+1)+j-1=i$, so the pyramid is nice.
     56 
     57 **Code in C++**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 using namespace std;
     62 int main() {
     63     int t;
     64     cin >> t;
     65     while (t--) {
     66         int n;
     67         cin >> n;
     68         for (int i = 1; i <= n; i++) {
     69             for (int j = 1; j <= i; j++) {
     70                 cout << (j == 1 || j == i) << ' ';
     71             }
     72             cout << '\n';
     73         }
     74     }
     75 }
     76 ```
     77 
     78 ## [1734C — Removing Smallest Multiples](https://codeforces.com/contest/1734/problem/C)
     79 
     80 One operation should be used to remove every element not belonging to $T$.
     81 
     82 Let $v$ be an element not belonging to $T$. Suppose a $x$-cost operation removes value $v$, then $v$ must be divisible by $x$. Furthermore, the multiples $x,2x,\cdots (k-1)x$ must have been already removed from $S$, where we write $v = kx$.
     83 
     84 Since removed elements stay removed, the above is only possible if all of $x,2x,\cdots (k-1)x$ does not belong to $T$.
     85 
     86 For each $v$, let $f(v)$ be the smallest integer $x$ satisfying the above condition. As we can always remove $v$ using a $v$-cost operation, $f(v) \leq v$ and in particular $f(v)$ exists.
     87 
     88 The total cost must be at least $\sum_{i \not \in T} f(i)$. We claim that this cost can be achieved.
     89 
     90 To do so, we should remove the required elements in ascending order. When removing $v$, we assume all $w \not\in T$ with $w \lt v$ have already been removed. At this state, an $f(v)$-cost operation would be able to remove $v$.
     91 
     92 It remains to find the values $f(v)$. To do so efficiently, we can perform the above process in a bottom-up manner similar to the Sieve of Eratosthenes. Please refer to the code below for implementation details. The overall complexity is $n (1 +\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}) = \Theta(n \log n)$.
     93 
     94 **Code in C++**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 using namespace std;
     99 void solve() {
    100     int n;
    101     cin >> n;
    102     bool a[n + 1];
    103     string str;
    104     cin >> str;
    105     for (int i = 1; i <= n; i++) {
    106         a[i] = (str[i - 1] == '1');
    107     }
    108     long long ans = 0;
    109     int cost[n + 1];
    110     for (int i = n; i >= 1; i--) {
    111         for (int j = i; j <= n; j += i) {
    112             if (a[j]) break;
    113             cost[j] = i;
    114         }
    115     }
    116     for (int i = 1; i <= n; i++) {
    117         if (!a[i]) ans += cost[i];
    118     }
    119     cout << ans << '\n';
    120 }
    121 int main() {
    122     int t;
    123     cin >> t;
    124     while (t--) solve();
    125 }
    126 ```
    127 
    128 ## [1734D — Slime Escape](https://codeforces.com/contest/1734/problem/D)
    129 
    130 Let's call a group of slime **good** if their total health is at least $0$, or if defeating this group allows you to reach the exits.
    131 
    132 We partition the slimes into good groups in a two-pointer like manner. To form the groups to the right, start from position $k$, then find the smallest position $r$ such that slimes from $k+1$ through $r$ form a good group. We do the same starting from $r+1$ again. Repeat this process until slimes to the right are partitioned into groups, which can be done by maintaining the sum of health. We partition the left slimes into groups in a similar way.
    133 
    134 We can observe that in an optimal strategy, we may assume the player absorbs group-by-group.
    135 
    136 **Proof**
    137 
    138 Assuming there is a valid strategy $S$ to reach the exit. Let $X$ be the first group to the left, and $Y$ be the first group to the right. Without loss of generality, assume all slimes of $X$ are absorbed before all slimes of $Y$ are absorbed first. Suppose there are $x$ slimes in $X$ and $y$ slimes in $Y$.
    139 
    140 Suppose we did not absorb all of $X$ at a time. For example, if there are $6$ slimes in $X$ and $5$ or more slimes in $Y$, the beginning of our strategy may look like this:
    141 
    142 $LLRRLRLLRL....$
    143 
    144 Consider instead the strategy where we move all `L' to the front. We claim that the strategy stays valid. That is, the following strategy
    145 
    146 $LLLLLLRRRR....$ is at least as good.
    147 
    148 We check that at every moment of strategy $LLLLLLRRRR....$, there is some point in time $LLRRLRLLRL....$ which we would have less than or equal amount of health.
    149 
    150 For the state $T_1$ that we take $a$ moves to the left in $LLLLLLRRRR....$, we compare it with any moment $T_2$ in $LLRRLRLLRL....$ that we have taken $a$ moves to the left. To reach $T_2$, we take $b$ moves to the right. We can check that under the assumption, $0 \leq b \lt y$. Since $Y$ is the smallest good group to the right, taking these $b$ extra right moves must have reduced our health. So, we have more health at $T_1$ than in $T_2$.
    151 
    152 Now consider the state $T_3$ in $LLLLLLRRRR....$ where we take all $x$ left moves and $b$ more right moves. We should compare it with any moment $T_4$ in $LLRRLRLLRL....$ that we have taken $b$ right moves and some $a$ left moves. We can check that under the assumption $0 \leq a \lt x$. Since $X$ is the smallest good group, taking only $a$ moves to the left gives us less health compared to taking all $x$ moves to the left. Therefore, we have more health at $T_3$ than in $T_4$.
    153 
    154 Therefore, if $LLRRLRLLRL....$ is valid, $LLLLLLRRRR....$ must be valid. So, we only need to consider strategies of the second form.
    155 
    156 By applying this claim recursively, we notice that we only need to consider strategies that absorb whole groups at a time.
    157 
    158 This works for all strategies, we just referred to the starting strategy as $LLRRLRLLRL....$, and the better strategy as $LLLLLLRRRR....$ to simplify notations.
    159 
    160 For any good group, since the total health is positive, there is no drawback to absorbing a good group. In other words, whenever it is possible to absorb a good group, we will absorb it.
    161 
    162 For each group $G$, we calculate the ``requirement'' of the group — the lowest health we can begin with, such that we can absorb the group while maintaining non-negative health at all times. The requirement of a group of slime with health $a_1,a_2 \cdots a_n$ can be expressed as
    163 
    164 $ - \min_{k=0}^n (\sum_{i=1}^k a_i)$
    165 
    166 Finally, we can simply simulate the process. We repeatedly attempt to absorb good groups to the left or to the right. We keep track of the current health, initially equal to $a_k$. Whenever we consider whether to absorb a group or not, we absorb it if and only if the current health is at least as high as its requirement. Otherwise, we ignore it for now and attempt to do so for the group on the other side. If it is possible to reach a state where either all left groups or all right groups are absorbed, then we can win the game. If at some point, it is not possible to absorb the left group nor the right group, then we lose.
    167 
    168 The overall complexity is $\Theta(n)$.
    169 
    170 It is also possible to use a range $\max$/$\min$ segment tree form the groups instead of using two-pointers, in which case its complexity would be $\Theta(n \log n)$.
    171 
    172 **Code in C++**
    173 
    174 ```
    175 #include <bits/stdc++.h>
    176 using namespace std;
    177 void solve() {
    178     long long n, k, P;
    179     cin >> n >> k;
    180     k--;
    181     long long L[n];
    182     for (int i = 0; i < n; i++) cin >> L[i];
    183     P = L[k];
    184     L[k] = 0;
    185     long long ps[n + 1];
    186     ps[0] = 0;
    187     for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + L[i - 1];
    188     int l = k, r = k + 1;
    189     vector<pair<long long, long long> > LG, RG;
    190     for (int i = k - 1; i >= 0; i--) {
    191         if (ps[i] <= ps[l] || i == 0) {
    192             long long worst = 0, cur = 0;
    193             for (int j = l - 1; j >= i; j--) {
    194                 cur += L[j];
    195                 worst = min(worst, cur);
    196             }
    197             LG.push_back({cur, -worst});
    198             l = i;
    199         }
    200     }
    201     for (int i = k + 2; i <= n; i++) {
    202         if (ps[i] >= ps[r] || i == n) {
    203             long long worst = 0, cur = 0;
    204             for (int j = r; j <= i - 1; j++) {
    205                 cur += L[j];
    206                 worst = min(worst, cur);
    207             }
    208             RG.push_back({cur, -worst});
    209             r = i;
    210         }
    211     }
    212     reverse(LG.begin(), LG.end());
    213     reverse(RG.begin(), RG.end());
    214     long long curp = P;
    215     while (true) {
    216         bool acted = false;
    217         if (!LG.empty() && curp >= LG.back().second) {
    218             curp += LG.back().first;
    219             LG.pop_back();
    220             acted = true;
    221         }
    222         if (!RG.empty() && curp >= RG.back().second) {
    223             curp += RG.back().first;
    224             RG.pop_back();
    225             acted = true;
    226         }
    227         if (LG.empty() || RG.empty()) {
    228             cout << "YES\n";
    229             return;
    230         }
    231         if (!acted) {
    232             cout << "NO\n";
    233             return;
    234         }
    235     }
    236 }
    237 int main() {
    238     int t;
    239     cin >> t;
    240     while (t--) solve();
    241 }
    242 ```
    243 
    244 ## [1734E — Rectangular Congruences](https://codeforces.com/contest/1734/problem/E)
    245 
    246 We say a matrix to be good if it satisfies the congruence condition (the second condition).
    247 
    248 When we have a good matrix, we can add any value $c$ to a whole row while maintaining the congruence relation. The same is true for adding the same value to a whole column.
    249 
    250 Suppose we have any good matrix $A$, then by adding $b_i - a_{i,i}$ to the $i$-th row for each of $i=1,2,\cdots,n$, we obtain a good matrix that has the desired values on the diagonal.
    251 
    252 In fact, there are a lot of possible constructions. We present a few of them here:
    253 
    254 * $a_{i,j} = i \times j \pmod n$
    255 * $a_{i,j} = (i + j)^2 \pmod n$. This needs special handling when $n=2$.
    256 * $a_{i,j} = \frac{(i+j)(i+j+1)}{2} \pmod n$.
    257 * The coolest part is that all quadratic polynomials in the form $ai^2 + bij + cj^2 + di + ej + f$ are valid for all integers $a,b,c,d,e,f$ and $b \not\equiv 0 \pmod n$
    258 
    259 As a bonus, we prove that the general quadratic polynomial gives a good construction.
    260 
    261 **Proof**
    262 
    263 Since we can add values to a whole row or column, and $i^2, j^2 , i , j , 1$ are also constant on the rows and columns, adding them by $a_{i,j}$ has no effect. So we may just assume $a = c = d =e = f =0$.
    264 
    265 So it suffices to show that $a_{i,j} = b i j \pmod n$ satisfies the condition. We can see directly that $a_{r_1,c_1} - a_{r_2,c_1} - a_{r_1,c_2} +a_{r_2,c_2} = b(r_1 - r_2)(c_1 - c_2)$. As $r_1 \neq r_2$, $c_1 \neq c_2$, $b \not\equiv 0 \pmod n$, and $n$ is a prime, this expression must be nonzero $\pmod n$.
    266 
    267 Here are some extra observations that may enable one to find a good matrix more quickly.
    268 
    269 **Some extra observations**
    270 
    271 For each $j$, the values $a_{i,j} - a_{i-1,j}$ over all $0 \le i \lt n $ must be a permutation of ${0,1,\cdots,n-1}$.
    272 
    273 A good matrix stays good if we permute the rows or permute the columns. Therefore, we can show that there exists some good matrix with $a_{1,j} = a_{i,1} = 0$, and $a_{2,j} = j-1$, $a_{i,2} = i-1$. Assuming this, it should not be difficult to discover $a_{i,j} = (i-1)(j-1)$ yields one of the good matrices.
    274 
    275 Let $b$ be the two dimensional difference array of $a$, that is, $b_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}$. Then, the condition becomes sum of any rectangles of $b$ must be nonzero $\pmod n$. It is easy to see $ b = 1$ is valid. This corresponds to the solution that $a_{i,j} = i \times j \pmod n$.
    276 
    277 **Code in C++**
    278 
    279 ```
    280 #include <bits/stdc++.h>
    281 using namespace std;
    282 
    283 int want[355];
    284 int board[355][355];
    285 int main() {
    286     int n;
    287     cin >> n;
    288     for(int i = 0; i < n ; i ++){
    289         cin >> want[i];
    290     }
    291     for (int i = 0; i < n; i++) {
    292         for (int j = 0; j < n; j++) {
    293             board[i][j] = (i * j) % n;
    294         }
    295     }
    296     for(int i = 0; i < n; i ++){
    297         int extra = (want[i] + n - board[i][i] )% n ;
    298         for (int j = 0; j < n; j++) {
    299             board[i][j] += extra;
    300             board[i][j] %= n;
    301         }
    302     }
    303     for (int i = 0; i < n; i++) {
    304         for (int j = 0; j < n; j++) {
    305             cout << board[i][j] << ' ';
    306         }
    307         cout << endl;
    308     }
    309 }
    310 ```
    311 
    312 ## [1734F — Zeros and Ones](https://codeforces.com/contest/1734/problem/F)
    313 
    314 Observe that the $i$-th character is `1' if and only if $i$ has an odd number of set bits in its binary representation. Both solutions make use of this fact.
    315 
    316 The constraints allows solutions of up to $\Theta(q \log^3 n)$. Yet, both of the model solution runs in $\Theta(\log n)$.
    317 
    318 ### 1. Digit DP solution
    319 
    320 The question can be reformulated as follows: How many integers $x$ between $0$ and $m-1$ inclusive have the property that the total number of set bits of $x$ and $x+n$ is an odd number?
    321 
    322 This can be solved with digit DP. We process the bit position from $\lceil \log(\max) \rceil$ down to $0$. We maintain three states:
    323 
    324 * $\text{ans}$, a boolean value;
    325 * $\text{trailzeros}$, an integer between $0$ and $\lceil \log(\max) \rceil$ inclusive; and
    326 * $\text{under}$, a boolean value.
    327 
    328 We can thus conclude the following: the number of trailing zeros is all we need to decide the answer.
    329 
    330 After processing each bit $k$, we should have the following: the number of integers $x$ between $0$ and $\lfloor \frac{m}{2^k} \rfloor$ inclusive which have the following property:
    331 
    332 * the total number of set bits of $x$ and $x + \lfloor \frac{n}{2^k} \rfloor$ is equal to $\text{ans} \mod 2$;
    333 * the number of trailing `1's of $x + \lfloor \frac{n}{2^k} \rfloor$ is equal to $\text{trailzeros}$;
    334 * the boolean value $[x \lt \lfloor \frac{m}{2^k} \rfloor]$ (where $[]$ is the Iverson bracket).
    335 
    336 Now onto the transitions. Suppose we are adding the $(k-1)$-th digit, and let $d$ be the new digit of $x$, and $z$ be the $(k-1)$-th digit of $n$.
    337 
    338 * If $z+d = 0$, then $(\text{ans},\text{trailzeros})$ after digit $k$ will be transited to $(\text{ans},0)$ after digit $k-1$;
    339 * if $z+d = 1$, then $(\text{ans},\text{trailzeros})$ after digit $k$ will be transited to $((\text{ans} + z +d) \mod 2, \text{trailzeros}+1)$ after digit $k-1$;
    340 * if $z+d =2$, then $(\text{ans},\text{trailzeros})$ after digit $k$ will be transited to $((\text{ans} + z + \text{trail} + 1) \mod 2, 0)$ after digit $k-1$
    341 
    342 The final answer is the total number of values for which $\text{ans} =1 $ and $\text{under} = 1$.
    343 
    344 The above solution runs in $\Theta(\log^2 (\max))$ per query. There is a simple way to optimize this to $\Theta(\log(\max))$: note that we only need to keep parity of $\text{trailzero}$.
    345 
    346 There are many other digit DP approaches that give similar time complexity. The constraints should allow most of them pass.
    347 
    348 **Code in Kotlin**
    349 
    350 ```
    351 val Boolean.chi:Int get() = if(this) 1 else 0 //characteristic function
    352 fun Int.has(i:Int):Boolean = (this and (1 shl i) != 0)
    353 fun Long.has(i:Int):Boolean = (this and (1L shl i) != 0L)
    354 fun main(){
    355     repeat(readLine()!!.toInt()){
    356 
    357         val (n,m) = (readLine()!!.split(" ").map { it.toLong() })
    358         var DP = Array(2){Array(2){LongArray(64)}}
    359 
    360         DP[0][0][0] = 1
    361 
    362         for(bit in 60 downTo 0 ){
    363             var new = Array(2){Array(2){LongArray(64)}}
    364             for(under in 0 until 2){
    365                 for(ans in 0 until 2){
    366                     for(nd in 0 until 2){
    367                         if(under == 0 && nd == 1 && !m.has(bit)) continue
    368                         val nunder = ((under == 1) || (nd == 0 && m.has(bit))).chi
    369 
    370                         val np = nd + n.has(bit).chi
    371 
    372                         for(trail in 0 until 62){
    373                             var nans = ans
    374                             if(nd == 1){
    375                                 nans = 1 - nans
    376                             }
    377                             var newtrail:Int
    378 
    379                             if(np == 0){
    380                                 newtrail = 0
    381                             }else if(np == 1){
    382                                 nans = 1 - nans
    383                                 newtrail = trail + 1
    384                             }else if(np == 2){
    385                                 nans = (nans + trail + 1) %2
    386                                 newtrail = 0
    387                             }else{
    388                                 error("oh no")
    389                             }
    390 
    391                             new[nunder][nans][newtrail] += DP[under][ans][trail]
    392                         }
    393                     }
    394                 }
    395             }
    396             DP = new
    397         }
    398 
    399         var ret = 0L
    400         for(trail in 0 until 64){
    401             ret += DP[1][1][trail]
    402         }
    403         println(ret)
    404 
    405     }
    406 }
    407 ```
    408 
    409 ### 2. Recursive Solution, by [darkkcyan](/profile/darkkcyan "Гроссмейстер darkkcyan")
    410 
    411 Define the function $f(x) := $ the parity of bit one in the number $x$.
    412 
    413 We have thus reworded the statement into evaluating the follow expression:
    414 
    415 $ T = \sum_{i = 0}^{k - 1} \left[f(i) \ne f(i + n)\right] $
    416 
    417 The formula can be further transformed as:
    418 
    419 $ T = \sum_{i = 0}^{k - 1} f(i \oplus (i + n)) $
    420 
    421 since $\left[ f(a) \ne f(b) \right] = f(a \oplus b)$ holds true for all non-negative integers $a$ and $b$.
    422 
    423 Imagine we construct a grid and assign the value at row $r$ and column $c$ to be $f(r \oplus c)$. Then, $T$ is sum of a diagonal of length $k$ which starts at either $(0, n)$ or $(n, 0)$. Without loss of generality, we use $(0, n)$ in this editorial.
    424 
    425 The grid can be constructed similarly to the way we construct the string $S$. We start with a $1$-by-$1$ matrix $M_0=\begin{bmatrix} 0 \end{bmatrix}$.
    426 
    427 Then, the matrix $M_i$ of size $2^i \times 2^i$ can be constructed as follows:
    428 
    429 $ M_i = \begin{bmatrix} M_{i - 1} & \overline {M_{i - 1}} \\ \overline{M_{i - 1}} & M_{i - 1} \end{bmatrix} $
    430 
    431 where $\overline{M_{i - 1}}$ is the matrix $M_{i - 1}$ but with flipped bits.
    432 
    433 Here is another way of constructing the grid: let $C_i$ be an infinite chess board with alternating colors, similar to a regular chess board, but with each of the cells being size $2^i \times 2^i$. For example, $C_0$, $C_1$ and $C_2$ in an $8$-by-$8$ grid is as follows:
    434 
    435 **Illustration**
    436 
    437 ```
    438 .*.*.*.*
    439 *.*.*.*.
    440 .*.*.*.*
    441 *.*.*.*.
    442 .*.*.*.*
    443 *.*.*.*.
    444 .*.*.*.*
    445 *.*.*.*.
    446 
    447 ..**..**
    448 ..**..**
    449 **..**..
    450 **..**..
    451 ..**..**
    452 ..**..**
    453 **..**..
    454 **..**..
    455 
    456 ....****
    457 ....****
    458 ....****
    459 ....****
    460 ****....
    461 ****....
    462 ****....
    463 ****....
    464 ```
    465 
    466 We claim that our grid is the $\text{xor}$ of all chess board $C_i$. The proof is easy: $C_i$ is constructed by $\text{xor}$-ing the $i$-th bit of the the row and column number.
    467 
    468 We are therefore motivated to proceed in the following way: if we drop the least significant bit (by making it to be $0$), we are still solving a very similar problem to the original problem, because dropping the first bit is similar to removing $C_0$. And when we shift $C_i$ to $C_{i - 1}$, it is a recursion of the same problem!
    469 
    470 Going back to the problem, where we are computing sum of a diagonal of length $k$. If $k$ is odd, we can make it odd by adding the last element to the result and decreasing $k$ by one. Now, $k$ is even, and we can utilize the recurrence as follows:
    471 
    472 * remove $C_0$.
    473 * scale the board down by 2 (including $n$ and $k$). By doing so, $C_i$ becomes $C_{i - 1}$.
    474 * solve the new problem.
    475 * scale the board up again and add $C_0$ back.
    476 * from the result of the scaled down problem, some how calculate the result of the original problem
    477 
    478 The result of the scaled down problem is the number of $2$-by-$2$ cells with value $1$. From the number of $2$-by-$2$ cells with value $1$, we compute the number of cells with value $0$ as well. It is not hard to observe that it crosses the $2$-by-$2$ cells at all places. The only thing that matters is the parity of $n$.
    479 
    480 * If $n$ is even, then the diagonal crosses the diagonal of the $2$-by-$2$ cells. In the scaled-down version, the diagonal is still a single diagonal starting at $(0, \frac{n}{2})$; otherwise,
    481 * if $n$ is odd, it crosses the corner of the $2$-by-$2$ cells. In the scaled-down version, the diagonal is actually $2$ neighboring diagonals starting at $(0, \frac{n-1}{2})$ and $(0, \frac{n+1}{2})$.
    482 
    483 Also, the $2$-by-$2$ cells with values $0$ and $1$ respectively will also have the form:
    484 
    485 **Illustration**
    486 
    487 ```
    488 .*    *.
    489 *.    .*
    490 ```
    491 
    492 From here we have everything we need to compute the result of the original problem.
    493 
    494 Overall, the number of states we have to visit is $\Theta(\log k)$.
    495 
    496 **Code in Python**
    497 
    498 ```
    499 import random
    500 
    501 cache = {}
    502 
    503 def popcount(n):
    504     res = 0
    505     while n:
    506         res += 1
    507         n &= n - 1
    508     return res
    509 
    510 def solve(n, k):
    511     if k == 0:
    512         return 0
    513     if k == 1:
    514         return popcount(n) & 1
    515     if k % 2 == 1:
    516         t = solve(n, k - 1)
    517         x = popcount((k - 1) ^ (n + k - 1)) & 1
    518         # print(t, x)
    519         return t + x
    520     if (n, k) in cache:
    521         return cache[(n, k)]
    522     if n % 2 == 0:
    523         one_cell = 2
    524         zero_cell = 0
    525         cnt1 = solve(n // 2, k // 2)
    526         cnt0 = k // 2 - cnt1
    527     else:
    528         one_cell = 0
    529         zero_cell = 1
    530         cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
    531         cnt0 = k - cnt1
    532     res = one_cell * cnt1 + zero_cell * cnt0
    533     # print(f"n = {n}, k = {k}, cnt1 = {cnt1}, cnt0 = {cnt0}, one_cell = {one_cell}, zero_cell = {zero_cell}")
    534     cache[(n, k)] = res
    535     return res
    536 
    537 t = int(input())
    538 for _ in range(t):
    539     cache.clear()
    540     n, k = map(int, input().split())
    541     print(solve(n, k))
    542 ```