codeforces-scrape

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

2180.md (39876B)


      1 Source: https://codeforces.com/blog/entry/149318
      2 
      3 Salam !
      4 
      5 Here is the editorial for [Codeforces Global Round 31](https://codeforces.com/contest/2180). We hope you find these solutions helpful. We also have prepared a special editorial with step by step hint, examples, tables, and walkthroughs which is available [here](https://repovive.com/editorial/codeforces-global-round-31).
      6 
      7 #### [2180A - Carnival Wheel](/contest/2180/problem/A)
      8 
      9 **Idea:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM"), [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
     10 
     11 **Solution**
     12 
     13 **Simple Simulation (Brute force)**
     14 
     15 Since constraints are small, we can simulate the spins directly:
     16 
     17 * Start from section $a$.
     18 * Move the pointer by adding $b$ modulo $l$ repeatedly.
     19 * Stop when we return to a previously visited section.
     20 * Among all visited sections, select the section with the highest prize.
     21 
     22 It runs in $\mathcal{O}(l)$ as we mark each section at most once.
     23 
     24 **Mathematical Solution (Using GCD)**
     25 
     26 It's easy to see that the pointer can land on section $c$ if $c \equiv a \pmod{d}$, where $d = \gcd(l, b)$. By Bézout's lemma, all such $c$ are indeed reachable. Hence, the maximum attainable section is:
     27 
     28 $ l - d + (a \bmod d). $
     29 
     30 **Implementation**
     31 
     32 ```
     33 // In the name of God
     34 #include <bits/stdc++.h>
     35 using namespace std;
     36 int main() {
     37     int l, a, b, t;
     38     cin >> t;
     39     while(t--) {
     40         cin >> l >> a >> b;
     41         cout << l - __gcd(l, b) + a % __gcd(l, b) << '\n'; 
     42     }
     43     return 0;
     44 }
     45 ```
     46 
     47 #### [2180B - Ashmal](/contest/2180/problem/B)
     48 
     49 **Idea:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM"), [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
     50 
     51 **Solution**
     52 
     53 * **Step 1**: It can be shown (for instance, via a contradiction argument) that, to obtain the lexicographically minimum final string $s$, we must ensure $s$ is lexicographically minimum at each intermediate step as well.
     54 * **Step 2:** Therefore, at every step $i$, we choose the lexicographically smaller result between adding $a_i$ to the beginning or the end of our current string.
     55 * **Step 3:** Initially, $s$ is the empty string. Suppose before step $i$, the current string is $s_i$. Then the best choice for the updated string is:
     56 
     57 $ \min(s_i + a_i,\ a_i + s_i). $
     58 
     59 * **Step 4:** By applying this choice at each step, we can compute the final (minimum) string in $\mathcal{O}(nS)$ where $S$ is the sum of string lengths.
     60 
     61 **Implementation**
     62 
     63 ```
     64 #include <bits/stdc++.h>
     65  
     66 using namespace std;
     67  
     68 int main() {
     69     ios_base::sync_with_stdio(false), cin.tie(nullptr);
     70     int t;
     71     cin >> t;
     72     while(t--) {
     73         int n;
     74         cin >> n;
     75         string s[n], t;
     76         for(int i = 0; i < n; i++)
     77             cin >> s[i];
     78         for(int i = 0; i < n; i++)
     79             t = min(t+s[i], s[i]+t);
     80         cout << t << '\n';
     81     }
     82     return 0;
     83 }
     84 ```
     85 
     86 #### [2180C - XOR-factorization](/contest/2180/problem/C)
     87 
     88 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
     89 
     90 **Solution**
     91 
     92 We build $a_1,\dots,a_k$ bit by bit from the highest bit to $0$.
     93 
     94 Let
     95 
     96 $ o(x)=\max\{t\le x:\ t\text{ odd}\},\qquad e(x)=\max\{t\le x:\ t\text{ even}\}. $
     97 
     98 Maintain two sets of indices:
     99 
    100 * $T$ (tight): current prefix of $a_i$ equals the prefix of $n$,
    101 * $L$ (loose): current prefix of $a_i$ is already smaller than the prefix of $n$.
    102 
    103 Initially, $T={1,\dots,k}$, $L=\emptyset$, and all $a_i=0$.
    104 
    105 **Greedy rule for each bit $b$ (from high to low).**
    106 
    107 * If the $b$-th bit of $n$ is $1$, then the number of $a_i$ having bit $b$ equal to $1$ must be **odd**. To maximize the sum we set as many ones as possible, i.e. exactly $o(k)$. So:
    108 
    109   + if $k$ is odd, set this bit in all $k$ numbers;
    110   + if $k$ is even, set it in all but one number. Prefer choosing that one from $T$ (if possible), because then it becomes loose ($T\to L$), which can help later.
    111 * If the $b$-th bit of $n$ is $0$, then the number of ones in this bit must be **even**. Tight indices cannot put $1$ here (otherwise $a_i \gt n$), so only $L$ may receive ones. Thus we set this bit in exactly $e(|L|)$ loose numbers (all of them if $|L|$ is even, otherwise all but one).
    112 
    113 **Why it is optimal.** At bit $b$, each extra chosen $1$ adds $2^b$ to the total sum, and this gain is larger than anything we can get from lower bits. Also, the XOR condition fixes the parity in every bit, so we can only change the number of $1$’s by removing them from an even number of elements. So, at every bit we should keep as many $1$’s as possible, as long as we do not violate $a_i\le n$. When the $b$-th bit of $n$ is $1$ and $k$ is even, we must place one $0$; choosing it from a tight index increases $|L|$, which can help us place more $1$’s later when $n$ has $0$-bits.
    114 
    115 This directly gives a construction with $0\le a_i\le n$, XOR equal to $n$, and maximum possible sum in $\mathcal{O}(k \log n)$.
    116 
    117 **Implementation**
    118 
    119 ```
    120 // In the name of god
    121 #include <bits/stdc++.h>
    122 using namespace std;
    123 typedef long long ll;
    124  
    125 int main() {
    126     ios_base::sync_with_stdio(false), cin.tie(nullptr);
    127     int t;
    128     cin >> t;
    129     while(t--) {
    130         int n, k;
    131         cin >> n >> k;
    132         int a[k]{}, p = 0;
    133         if(k&1)
    134             for(int i = 0; i < k; i++)
    135                 a[i] = n;
    136         else {
    137             for(int i = 30; i >= 0; i--) {
    138                 if(n >> i & 1) {
    139                     for(int j = 0; j < k; j++)
    140                         if(j != min(p, k-1))
    141                             a[j] += (1 << i);
    142                     if(p < k)
    143                         p++;
    144                 } else
    145                     for(int j = 0; j < p/2*2; j++)
    146                         a[j] += (1 << i);
    147             }
    148         }
    149         for(int i = 0; i < k; i++)
    150             cout << a[i] << (i+1 == k? '\n':' ');
    151     }
    152     return 0;
    153 }
    154 ```
    155 
    156 #### [2180D - Insolvable Disks](/contest/2180/problem/D)
    157 
    158 **Idea:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM"), [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
    159 
    160 **Solution**
    161 
    162 Let $x_1, x_2, \ldots, x_n$ be the sorted list of points, and let $d_i \ (1 \le i \le n-1)$ be the distance between consecutive points, i.e.
    163 
    164 $ d_i = x_{i+1} - x_i. $
    165 
    166 We try to find the largest prefix of points that can be made connected.
    167 
    168 Consider some valid choice of radii, and assume that the radius of the first disk is $r_1 = x$. In order for the second disk to be tangent to the first one, its radius must be
    169 
    170 $ r_2 = d_1 - x. $
    171 
    172 Continuing in this way, the third disk must have radius
    173 
    174 $ r_3 = d_2 - (d_1 - x) = d_2 - d_1 + x. $
    175 
    176 In general, if we connect the first $k$ disks together, the radius of the $i$-th disk $(1 \le i \le k)$ must be
    177 
    178 $ r_i = d_{i-1} - d_{i-2} + d_{i-3} - \cdots + (-1)^i d_1 + (-1)^{i+1} x. $
    179 
    180 For this configuration to be valid, we must have
    181 
    182 $ 0 \lt r_i \lt d_i. $
    183 
    184 Substituting the expression for $r_i$, we obtain
    185 
    186 $ 0 \lt d_{i-1} - d_{i-2} + d_{i-3} - \cdots + (-1)^i d_1 + (-1)^{i+1} x \lt d_i. $
    187 
    188 For odd $i$, this inequality becomes
    189 
    190 $ 0 \lt d_{i-1} - d_{i-2} + d_{i-3} - \cdots - d_1 + x \lt d_i, $
    191 
    192 which is equivalent to
    193 
    194 $ -d_{i-1} + d_{i-2} - d_{i-3} + \cdots + d_1 \lt x \lt d_i - d_{i-1} + d_{i-2} - d_{i-3} + \cdots + d_1. $
    195 
    196 For even $i$, we obtain
    197 
    198 $ 0 \lt d_{i-1} - d_{i-2} + d_{i-3} - \cdots + d_1 - x \lt d_i, $
    199 
    200 which is equivalent to
    201 
    202 $ -d_i + d_{i-1} - d_{i-2} + d_{i-3} - \cdots + d_1 \lt x \lt d_{i-1} - d_{i-2} + d_{i-3} - \cdots + d_1. $
    203 
    204 Therefore, for each $i$ we obtain an interval of valid values for $x$. By iterating over $i$ and maintaining the intersection of all these intervals, we can determine the first index where the intersection becomes empty. This index gives the largest prefix of disks that can be made connected.
    205 
    206 After removing these disks, we can repeat the same process on the remaining ones. It can be shown that this procedure finds the correct answer and runs in $O(n)$ time.
    207 
    208 **Why it is optimal.**
    209 
    210 For each index $i$, let $f_i$ be the rightmost position such that, for every $j$ with $i \le j \lt f_i$, we can simultaneously make the $j$-th disk tangent to the $(j+1)$-th disk. Thus, $f$ is increasing sequence.
    211 
    212 With this notation, the problem becomes selecting indices $1=i_1 \lt i_2 \lt \cdots \lt i_k$ such that
    213 
    214 $ f_{i_t}+1 \ge i_{t+1}\quad (1\le t \lt k) \qquad\text{and}\qquad f_{i_k}=n. $
    215 
    216 By induction, we may assume $i_{t+1}=f_{i_t}+1$, because choosing any smaller $i_{t+1}\le f_{i_t}+1$ cannot extend the reachable prefix beyond $f_{i_t}$, while choosing exactly $f_{i_t}+1$ is the earliest index that can potentially increase the farthest reachable position. Hence this greedy choice is optimal. Also, note that once we set $i_{t+1}=f_{i_t}+1$, there are no additional constraints on the choice of $r_{i_{t+1}}$ coming from earlier indices. In particular, any restriction on $r_{i_{t+1}}$ can only be imposed by $i_{t+1}+1$ (otherwise $f_{i_t}$ would not have been maximal by definition).
    217 
    218 **Implementation**
    219 
    220 ```
    221 #include <bits/stdc++.h>
    222  
    223 using namespace std;
    224  
    225 int main(){
    226     ios::sync_with_stdio(false) , cin.tie(0);
    227     int tt;
    228     cin >> tt;
    229     while(tt--){
    230         int n;
    231         cin >> n;
    232         int x[n];
    233         for(int i = 0 ; i < n ; i++) cin >> x[i];
    234         int ans = n-1;
    235         int l = 0 , r = +1e9+1;
    236         int cur = 0;
    237         int fst = 1;
    238         for(int i = 1 ; i < n ; i++){
    239             cur = (x[i] - x[i-1]) - cur;
    240             if(i % 2 == fst % 2){
    241                 r = min(r , cur);
    242                 if(i < n-1) l = max(l , cur - (x[i+1] - x[i]));
    243             }
    244             else{
    245                 l = max(l , -cur);
    246                 if(i < n-1) r = min(r , (x[i+1] - x[i]) - cur);
    247             }
    248             if(l >= r){
    249                 ans--;
    250                 l = 0 , r = +1e9+1;
    251                 cur = 0;
    252                 fst = i+1;
    253             }
    254         }
    255         cout << ans << endl;
    256     }
    257 }
    258 ```
    259 
    260 #### [2180E - No Effect XOR](/contest/2180/problem/E)
    261 
    262 **Idea:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
    263 
    264 **Solution**
    265 
    266 **Bitwise Approach**
    267 
    268 **Step 0.** Let us consider $0$ as valid answer, for $l=r$ it's the only value, so assume $l \lt r$. Also xor is a bijection, so if $[l,r]$ maps to itself then its complement in $\mathbb W$ (all non-negative integers) also maps to itself.
    269 
    270 **Step 1.** Let's count the number of $x$ such that maps $[0,n)$ to itself. If $n=2^k$ then every $0\le x \lt n$ works. If $2^{k-1} \lt n \lt 2^k$, then the $(k-1)$-th bit of $x$ must be $0$; otherwise it maps $2^k-1$ into $[0,n)$, hence the answer equals the answer for $[0, n-2^{k-1})$. Therefore the answer is simply the largest power of two dividing $n$.
    271 
    272 **Step 2.** Choose $k$ with $2^{k-1}\le r \lt 2^k$. If $2^{k-1} \le l \lt r \lt 2^k$, then every number in $[l,r]$ has the $(k-1)$-th bit equal to $1$, so subtracting $2^{k-1}$ from both ends just removes that common bit and does not change the answer; repeating this reduction, we may assume $0 \le l \lt 2^{k-1} \le r \lt 2^k$.
    273 
    274 **Step 3.** Work in the block $[0,2^k-1]$ and define $A=[0,l-1]$, $B=[l,r]$, $C=[r+1,2^k-1]$. We need $B\oplus x=B$. In this crossing case, every element of $A$ has $(k-1)$-th bit $0$ and every element of $C$ has $(k-1)$-th bit $1$, so xor by $x$ cannot send only part of $A$ to $C$. Since xor is a bijection on the whole block, once $B$ maps to itself we must also map $A\cup C$ to itself, and there are only two possibilities:
    275 
    276 * **Map $A\to A$, $B\to B$, $C\to C$.** This is equivalent to simultaneously keeping the prefix $A=[0,l)$ invariant and also keeping the prefix $A\cup B=[0,r+1)$ invariant.
    277 * **Map $A\to C$ and $C\to A$, while still $B\to B$.** This is possible only if $|A|=|C|$. Define $\bar{x}=x\oplus(2^k-1)$. Then for every $x$ that maps $A$ to $A$, the value $\bar{x}$ maps $A$ to $C$, and vice versa, since $2^k-1=(11\ldots 1)_2$ acts like a mirror on $[0,2^k)$.
    278 
    279 **Linear Algebra Approach (Guessing a basis)**
    280 
    281 Let $S$ be the set of all valid $x$ (including $0$). We claim that $S$ is closed under XOR. Assume $x,y\in S$. By validity, for every $i\in[l,r]$ we have
    282 
    283 $ l \le i\oplus x \le r \quad\text{and}\quad l \le (i\oplus x)\oplus y \le r. $
    284 
    285 But $(i\oplus x)\oplus y = i\oplus (x\oplus y)$, hence for all $i\in[l,r]$,
    286 
    287 $ l \le i\oplus (x\oplus y) \le r, $
    288 
    289 so $x\oplus y\in S$. Therefore $S$ forms a vector space over $\mathbb{F}_2$, and it is enough to find a basis.
    290 
    291 Consider
    292 
    293 $ f_n(x) := x \oplus (2^n-1). $
    294 
    295 For $0\le x \lt 2^n$ we have
    296 
    297 $ x\oplus(2^n-1) = x\oplus(111\ldots1)_2 = 2^n-1-x, $
    298 
    299 so $f_n$ acts like a mirror inside each block of length $2^n$. Motivated by this, we guess that basis elements are of the form $(111\ldots1)_2$, i.e. $2^n-1$.
    300 
    301 Now we determine for which $n$ we have $2^n-1\in S$. Define the blocks
    302 
    303 $ b_k := [k\cdot 2^n,(k+1)\cdot 2^n). $
    304 
    305 If $r-l+1 \gt 2^n$, then $2^n-1$ is valid if and only if for every $k$, the intersection $[l,r]\cap b_k$ is either empty or the whole block $b_k$ (equivalently, $[l,r]$ never cuts a block partially), since $f_n$ preserves each block and reverses the order inside it.
    306 
    307 We must also check one boundary case, where $f_n$ maps $[l,r]$ to itself, which happens only if:
    308 
    309 $l \oplus (2^n-1) = r \Rightarrow l \oplus r = 2^n-1$ $\lfloor \frac{l}{2^n} \rfloor = \lfloor \frac{r}{2^n} \rfloor $ $l \neq k \cdot 2^n \text{ (Counted before)}$
    310 
    311 In other words, $l$ and $r$ must be symmetric with respect to the midpoint of one block under the mirror $f_n$.
    312 
    313 **Implementation**
    314 
    315 ```
    316 // In the name of god
    317 #include <bits/stdc++.h>
    318 using namespace std;
    319 typedef long long ll;
    320  
    321 inline ll maxPower2Multiple(const ll &a) {return a&-a;}
    322 inline ll prefixAnswer(const ll &a) {return maxPower2Multiple(a);}
    323 inline bool isPerfect(const ll &a) {return a == maxPower2Multiple(a);}
    324  
    325 int main() {
    326     ios_base::sync_with_stdio(false), cin.tie(nullptr);
    327     int t;
    328     cin >> t;
    329     while(t--) {
    330         ll l, r;
    331         cin >> l >> r;
    332         ll both = 1LL<<60;
    333         while((both&l) == (both&r) && both > 0) {
    334             if(both&l) l -= both, r -= both;
    335             both >>= 1;
    336         }
    337         if(l and isPerfect(l+r+1))
    338             cout << 2LL*min(prefixAnswer(l), prefixAnswer(r+1LL))-1LL << '\n';
    339         else if(l)
    340             cout << min(prefixAnswer(l), prefixAnswer(r+1LL))-1LL << '\n';
    341         else
    342             cout << prefixAnswer(r+1LL)-1LL << '\n';
    343     }
    344     return 0;
    345 }
    346 ```
    347 
    348 #### [2180F1 - Control Car (Easy Version)](/contest/2180/problem/F1)
    349 
    350 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
    351 
    352 **Solution**
    353 
    354 We solve the problem using dynamic programming.
    355 
    356 A naive DP definition would be to let $dp[i][j]$ be the probability that a car, currently at cell $(i,j)$, eventually reaches the bottom-right corner of the grid. However, this state does not contain enough information to determine valid transitions, since the future movement of the car depends on the direction from which it entered the current cell and on the orientations of certain walls. Therefore, we need to add more information to our DP states.
    357 
    358 We define the following DP states:
    359 
    360 * $dp[i][j][0][0]$: the probability that the car reaches the bottom-right corner, given that it is currently at cell $(i,j)$, entered this cell from above, and the wall starting from the top-right corner of this cell is pointing downward.
    361 * $dp[i][j][0][1]$: similar to $dp[i][j][0][0]$, but the wall starting from the top-right corner of the cell is \textbf{not} pointing downward.
    362 * $dp[i][j][1][0]$: the probability that the car reaches the bottom-right corner, given that it is currently at cell $(i,j)$, entered this cell from the left, and the wall starting from the bottom-left corner of this cell is pointing to the right.
    363 * $dp[i][j][1][1]$: similar to $dp[i][j][1][0]$, but the wall starting from the bottom-left corner of the cell is \textbf{not} pointing to the right.
    364 
    365 We now describe how to compute the transitions.
    366 
    367 Consider the state $dp[i][j][0][0]$. In this case, the car is at cell $(i,j)$, it entered from above, and the top-right wall is pointing downward. Therefore, the car cannot move to cell $(i,j+1)$ and must move to cell $(i+1,j)$.
    368 
    369 After moving to $(i+1,j)$, there is a probability of $\frac{3}{16}$ that the top-right wall of the new cell is pointing downward, and a probability of $\frac{3}{8}$ that it is not. Thus, we obtain
    370 
    371 $ dp[i][j][0][0] = \frac{3}{16} \, dp[i+1][j][0][0] + \frac{3}{8} \, dp[i+1][j][0][1]. $
    372 
    373 Using similar arguments for the remaining states, we get the following transitions:
    374 
    375 $ dp[i][j][0][1] = \frac{3}{16} \, dp[i+1][j][0][0] + \frac{3}{8} \, dp[i+1][j][0][1] + \frac{1}{16} \, dp[i][j+1][1][0] + \frac{5}{16} \, dp[i][j+1][1][1], $ $ dp[i][j][1][0] = \frac{3}{16} \, dp[i][j+1][1][0] + \frac{3}{8} \, dp[i][j+1][1][1], $ $ dp[i][j][1][1] = \frac{1}{2} \, dp[i+1][j][0][1] + \frac{1}{4} \, dp[i+1][j][0][0] + \frac{3}{16} \, dp[i][j+1][1][1]. $
    376 
    377 By computing these DP states in reverse order of $i$ and $j$, we can evaluate all states in $O(nm)$ time and obtain the final answer.
    378 
    379 **Implementation**
    380 
    381 ```
    382 // In the name of god
    383 #include <bits/stdc++.h>
    384  
    385 using namespace std;
    386 typedef long long ll;
    387  
    388 constexpr int T = 10000; 
    389 constexpr int N = 5000;
    390 constexpr ll mod = 1000000007;
    391 constexpr ll inv2 = (mod+1)>>1;
    392 constexpr ll inv4 = inv2>>1;
    393 constexpr ll inv8 = inv4>>1;
    394 constexpr ll inv16 = (inv8+mod)>>1;
    395 ll dp[2][N+1][2][2];
    396 vector<pair<int, int>> query[N+1];
    397 ll ans[T];
    398  
    399 inline ll Pow(ll a, ll b) {
    400     ll res = 1LL;
    401     b %= mod-1;
    402     while(b) {
    403         if(b&1) res = (res*a)%mod;
    404         a = (a*a)%mod; 
    405         b >>= 1;
    406     }
    407     return res;
    408 }
    409  
    410 int main() {
    411     ios_base::sync_with_stdio(false), cin.tie(nullptr);
    412     int t;
    413     cin >> t;
    414     for(int n, m, i = 0; i < t; i++) {
    415         cin >> n >> m;
    416         query[n].push_back({m, i});
    417     }
    418 	for(int i = 0; i <= N; i++)
    419 		dp[N&1][i][0][0] = dp[N&1][i][0][1] = dp[N&1][i][1][0] = dp[N&1][i][1][1] = 1;
    420     for(int i = N-1; i >= 0; i--) {
    421         int q = i&1, p = 1-(i&1);
    422 		dp[q][N][0][0] = dp[q][N][0][1] = dp[q][N][1][0] = dp[q][N][1][1] = 1;
    423         for(int j = N-1; j >= 0; j--) {
    424             dp[q][j][0][0] = (dp[p][j][0][0]*3LL*inv16+dp[p][j][0][1]*3LL*inv8)%mod;
    425             dp[q][j][0][1] = ((dp[p][j][0][0]*3LL*inv16+dp[p][j][0][1]*3LL*inv8)%mod+
    426                                 dp[q][j+1][1][0]*inv16+dp[q][j+1][1][1]*5LL*inv16)%mod;
    427             dp[q][j][1][0] = (dp[q][j+1][1][0]*3LL*inv16+dp[q][j+1][1][1]*3LL*inv8)%mod;
    428             dp[q][j][1][1] = (dp[p][j][0][0]*inv4+dp[p][j][0][1]*inv2+dp[q][j+1][1][1]*3LL*inv16)%mod;
    429         }
    430         for(auto [m, qu]: query[N-i]) {
    431             ll P = (dp[q][N-m][0][0]*inv4+dp[q][N-m][0][1]*3LL*inv4)%mod;
    432             ans[qu] = (1LL-P+mod)*Pow(4LL, 1LL*(N-i+1)*(m+1))%mod;
    433         }
    434     }
    435     for(int i = 0; i < t; i++)
    436         cout << ans[i] << '\n';
    437     return 0;
    438 }
    439 ```
    440 
    441 #### [2180F2 - Control Car (Hard Version)](/contest/2180/problem/F2)
    442 
    443 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
    444 
    445 **Solution**
    446 
    447 Note that the $j$-th layer of DP states (that is, $dp[i][j]$ for all valid $i$) depends only on the $(j-1)$-th layer and the $j$-th layer itself. Moreover, all layers are computed using identical transition rules.
    448 
    449 Let $dp[j]$ denote the vector consisting of all states $dp[i][j]$ for a fixed $j$. Then there exists a constant transition matrix $M$ such that
    450 
    451 $ dp[j] = M \cdot dp[j-1]. $
    452 
    453 By computing $M^{\,m-1}$ and multiplying it by the initial vector $dp[1]$, we obtain $dp[m]$, from which the final answer can be extracted.
    454 
    455 This can be done in $O(n^3 \log m)$ time using binary exponentiation.
    456 
    457 **Implementation**
    458 
    459 ```
    460 // In the name of god
    461 #include <bits/stdc++.h>
    462  
    463 using namespace std;
    464 typedef long long ll;
    465  
    466 constexpr ll N = 50 + 1;
    467 constexpr ll M = 1000000000000000LL;
    468 constexpr ll mod = 1000000007;
    469 constexpr ll inv2 = (mod+1)>>1;
    470 constexpr ll inv4 = inv2>>1;
    471 constexpr ll inv8 = inv4>>1;
    472 constexpr ll inv16 = (inv8+mod)>>1;
    473 ll n, m;
    474  
    475 struct DP {
    476     ll dp[N][2][2][N][2][2] = {};
    477 };
    478  
    479 inline DP upd(const DP& l, const DP& r) {
    480     DP lr;
    481     for(int li = 0; li <= n; li++)
    482         for(int lh = 0; lh < 2; lh++)
    483             for(int lk = 0; lk < 2; lk++)
    484                 for(int ri = li; ri <= n; ri++)
    485                     for(int rh = 0; rh < 2; rh++)
    486                         for(int rk = 0; rk < 2; rk++) 
    487                             for(int mi = li; mi <= ri; mi++) {
    488                                 for(int mh = 0; mh < 2; mh++)
    489                                     for(int mk = 0; mk < 2; mk++)
    490                                         lr.dp[li][lh][lk][ri][rh][rk] += l.dp[li][lh][lk][mi][mh][mk]*r.dp[mi][mh][mk][ri][rh][rk];
    491                                 lr.dp[li][lh][lk][ri][rh][rk] %= mod;
    492                             }
    493     return lr;
    494 }
    495  
    496 inline DP Identical() {
    497     DP I;
    498     for(int i = 0; i < n; i++)
    499         for(int j = 0; j < 2; j++)
    500             for(int k = 0; k < 2; k++)
    501                 I.dp[i][j][k][i][j][k] = 1;
    502     return I;
    503 }
    504  
    505 inline DP Pow(DP a, ll b) {
    506     DP res = Identical();
    507     while(b) {
    508         if(b&1) res = upd(res, a);
    509         a = upd(a, a);
    510         b >>= 1;
    511     }
    512     return res;
    513 }
    514  
    515 inline ll Pow(ll a, ll b) {
    516     ll res = 1LL;
    517     while(b) {
    518         if(b&1) res = res*a%mod;
    519         a = a*a%mod;
    520         b >>= 1;
    521     }
    522     return res;
    523 }
    524  
    525 int main() 
    526 {
    527     int t;
    528     cin >> t;
    529     while(t--) {
    530         cin >> n >> m;
    531         DP col;
    532     	col.dp[n][0][0][n][0][0] = col.dp[n][0][1][n][0][1] = col.dp[n][1][0][n][1][0] = col.dp[n][1][1][n][1][1] = 1;
    533         for(int i = (int)n-1; i >= 0; i--) {
    534             for(int j = i+1; j <= n; j++)
    535                 for(int k = 0; k < 2; k++)
    536                     for(int l = 0; l < 2; l++) {
    537                         col.dp[i][0][1][j][k][l] = col.dp[i][0][0][j][k][l] = (col.dp[i+1][0][0][j][k][l]*3LL*inv16+col.dp[i+1][0][1][j][k][l]*3LL*inv8)%mod;
    538                         col.dp[i][1][1][j][k][l] = (col.dp[i+1][0][0][j][k][l]*inv4+col.dp[i+1][0][1][j][k][l]*inv2)%mod;
    539                     }
    540             col.dp[i][0][1][i][1][0] = inv16;
    541             col.dp[i][0][1][i][1][1] = 5LL*inv16%mod;
    542             col.dp[i][1][0][i][1][0] = 3LL*inv16%mod;
    543             col.dp[i][1][0][i][1][1] = 3LL*inv8%mod;
    544             col.dp[i][1][1][i][1][1] = 3LL*inv16; 
    545         }
    546         DP dpnm = Pow(col, m);
    547         ll ans = 0;
    548         for(int i = 0; i <= n; i++)
    549             for(int j = 0; j < 2; j++)
    550                 for(int k = 0; k < 2; k++)
    551                     ans = (ans+dpnm.dp[0][0][0][i][j][k]*inv4+dpnm.dp[0][0][1][i][j][k]*3LL*inv4)%mod;
    552         cout << (1LL-ans+mod)*Pow(4LL, 1LL*(n+1LL)*(m+1LL))%mod << '\n';
    553     }
    554     return 0;
    555 }
    556 ```
    557 
    558 #### [2180G - Balance](/contest/2180/problem/G)
    559 
    560 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM"), [Shayan](/profile/Shayan "International Grandmaster Shayan") — **Preparation:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
    561 
    562 **Solution**
    563 
    564 First, note that due to the structure of the queries, the array $a$ is always a palindrome.
    565 
    566 Let $n$ be the current length of the array. Define $c_{i,m,k}$ as the number of subsequences of $a$ of length $m$ in which $a_i$ appears as the $k$-th element. Then the total sum of balances over all non-empty subsequences is equal to
    567 
    568 $ \sum_{i=1}^{n} \sum_{m=1}^{n} \sum_{k=1}^{m} a_i \cdot c_{i,m,k} \cdot \frac{k}{m}. $
    569 
    570 By symmetry of the palindrome, we have
    571 
    572 $ c_{i,m,k} = c_{n-i+1,m,m-k+1}. $
    573 
    574 Using this symmetry, we can write
    575 
    576 $ 2 \cdot \text{balance} = \sum_{i,m,k} a_i \cdot c_{i,m,k} \cdot \frac{k}{m} + \sum_{i,m,k} a_{n-i+1} \cdot c_{n-i+1,m,m-k+1} \cdot \frac{m-k+1}{m}. $
    577 
    578 After rearranging terms, this implies that the total balance can be decomposed into two parts:
    579 
    580 * the sum of all elements over all non-empty subsequences,
    581 * plus the sum of averages of all non-empty subsequences.
    582 
    583 The first part is straightforward. Each element $a_i$ appears in exactly $2^{n-1}$ non-empty subsequences, hence
    584 
    585 $ \sum_{\text{all subsequences}} \sum a_i = 2^{n-1} \sum_{i=1}^{n} a_i. $
    586 
    587 For the second part, note that $a_i$ contributes to subsequences of length $k$ exactly $\binom{n-1}{k-1}$ times, and in such subsequences its coefficient in the average is $\frac{1}{k}$. Therefore,
    588 
    589 $ \sum_{i=1}^{n} \sum_{k=1}^{n} a_i \cdot \frac{\binom{n-1}{k-1}}{k} = \sum_{i=1}^{n} a_i \cdot \sum_{k=1}^{n} \frac{\binom{n-1}{k-1}}{k}. $
    590 
    591 It is easy to verify that
    592 
    593 $ \sum_{k=1}^{n} \frac{\binom{n-1}{k-1}}{k} = \frac{2^n-1}{n}. $
    594 
    595 Hence the second part equals
    596 
    597 $ \frac{2^n-1}{n} \sum_{i=1}^{n} a_i. $
    598 
    599 Combining both parts, if we denote
    600 
    601 $ S = \sum_{i=1}^{n} a_i, $
    602 
    603 the answer to a type $3$ query is
    604 
    605 $ 2^{n-1} \cdot S + \frac{2^n-1}{n} \cdot S. $
    606 
    607 Thus, it is sufficient to maintain the values of $n$ and $S$. Since all computations are done modulo $10^9+7$, we maintain:
    608 
    609 * $S \bmod (10^9+7)$,
    610 * $n \bmod (10^9+7)$,
    611 * $n \bmod (10^9+6)$ (for computing powers of $2$).
    612 
    613 Updating $S$ and $n$ for queries of type $2$ is trivial. Updating $n$ for queries of type $1$ is also straightforward. The only non-trivial part is determining which element is removed in a type $1$ query in order to update $S$.
    614 
    615 To handle this, consider a type $2$ query inserting a value $x$. There are two cases.
    616 
    617 * If the current length of $a$ is odd ($2n+1$), after insertion the array becomes
    618 
    619 $ [x, a_1, x, \ldots, x, a_{n+1}, x, \ldots, x, a_{2n+1}, x]. $
    620 
    621 The first time the middle element is removed, it is the original middle element of $a$. The next two times, the removed element is $x$. After that, the situation is equivalent to applying the same process to the array obtained by removing the middle element of $a$.
    622 
    623 * If the current length of $a$ is even ($2n$), after insertion the array becomes
    624 
    625 $ [x, a_1, x, \ldots, a_n, x, a_{n+1}, x, \ldots, a_{2n}, x]. $
    626 
    627 The first removed middle element is $x$, the second one is the original middle element of $a$ (namely $a_{n+1}$), and afterwards the situation again reduces to the same process on the array with its middle element removed.
    628 
    629 Using this observation, we maintain a list of all values added by type $2$ queries, in order. For each such value we store an integer state in ${0,1,2,3}$. When a new value $x$ is inserted:
    630 
    631 * if the current length is odd, we assign it state $3$,
    632 * otherwise, we assign it state $1$.
    633 
    634 When processing a type $1$ query, we traverse this list from the end. For each element:
    635 
    636 * if its state is $0$ or $1$, this element is the current middle element; we update its state to $(\text{state}+1)\bmod 4$ and return its value,
    637 * otherwise, we only update its state to $(\text{state}+1)\bmod 4$ and continue.
    638 
    639 This procedure finds the middle element in $O(1)$ amortized time per query.
    640 
    641 Therefore, the overall time complexity of the solution is $O(q \log M)$.
    642 
    643 **Implementation**
    644 
    645 ```
    646 #include <bits/stdc++.h>
    647  
    648 using namespace std;
    649  
    650 long long pw(long long a , long long b , long long mod){
    651   long long ret = 1;
    652   long long mul = a;
    653   while(b > 0){
    654 	if(b&1)
    655 	  ret = (ret * mul) % mod;
    656 	mul = (mul * mul) % mod;
    657 	b >>= 1;
    658   }
    659   return ret;
    660 }
    661  
    662 const int mod = 1e9 + 7;
    663  
    664 int q;
    665  
    666 int sum = 0 , lenm = 0 , lenm1 = 0 , len2 = 0;
    667  
    668 vector<pair<int,int>> adds; // stay stay pass pass
    669  
    670 int get(int id , int del = 1){
    671     assert(id >= 0);
    672     if(adds[id].second < 2){
    673         if(del) adds[id].second = (adds[id].second + 1) & 3;
    674         return adds[id].first;
    675     }
    676     else{
    677         if(del) adds[id].second = (adds[id].second + 1) & 3;
    678         return get(id-1 , del);
    679     }
    680 }
    681  
    682 int main() 
    683 {
    684     ios::sync_with_stdio(false) , cin.tie(0);
    685     int tt;
    686     cin >> tt;
    687     while(tt--){
    688         cin >> q;
    689         sum = 0 , lenm = 0 , lenm1 = 0 , len2 = 0;
    690         adds.clear();
    691         while(q--){
    692             int tp;
    693             cin >> tp;
    694             if(tp == 1){
    695                 sum = (sum - get(adds.size()-1 , 1) + mod) % mod;
    696                 lenm = (lenm - 1 + mod) % mod;
    697                 lenm1 = (lenm1 - 1 + (mod-1)) % (mod-1);
    698                 len2 ^= 1;
    699             }
    700             else if(tp == 2){
    701                 int x;
    702                 cin >> x;
    703                 if(len2 == 1) adds.push_back({x , 3});
    704                 else adds.push_back({x , 1});
    705                 sum = (sum + 1ll * (lenm + 1) * x) % mod;
    706                 lenm = (2 * lenm + 1) % mod;
    707                 lenm1 = (2 * lenm1 + 1) % (mod-1);
    708                 len2 = 1;
    709             }
    710             else if(tp == 3){
    711                 int ans = (pw(2 , (lenm1 - 1 + (mod-1)) % (mod-1) , mod) + 1ll * (pw(2 , lenm1 , mod) - 1) * pw(lenm , mod-2 , mod)) % mod;
    712                 ans = (1ll * ans * sum) % mod;
    713                 ans = (1ll * ans * pw(2 , mod-2 , mod)) % mod;
    714                 cout << ans << endl;
    715             }
    716         }
    717     }
    718     return 0;
    719 }
    720 ```
    721 
    722 #### [2180H1 - Bug Is Feature (Unconditional Version)](/contest/2180/problem/H1)
    723 
    724 **Idea:** [Akulyat](/profile/Akulyat "Grandmaster Akulyat") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
    725 
    726 **Solution**
    727 
    728 **Step 1: reduce to independent series.**
    729 
    730 First, we can split the whole match into independent series $(a_i,b_i,c_i,[l_i,r_i])$. Since moves never mix two different games, by the Sprague-Grundy theorem we can compute the Grundy number contributed by each series and then solve the question.
    731 
    732 **Step 2: normalize one game.**
    733 
    734 Fix one game with upper bound $x$. Shift everything by $a$:
    735 
    736 $ (a,b,c,x)\ \longrightarrow\ (0,\ b-a,\ c-a,\ x-a). $
    737 
    738 Because $a,b,c$ are an arithmetic progression, we have $c-a=2(b-a)$. Put $d=b-a$ and $y=x-a$, so the state starts as
    739 
    740 $ (0,\ d,\ 2d,\ y). $
    741 
    742 Any move keeps the three numbers in an arithmetic progression (after reordering). In this normalized form, every legal move transforms $(0,\ d,\ 2d,\ y)$ into exactly one of the following forms: - $(d,\ 2d,\ 3d,\ y)$, - $(0,\ 2d,\ 4d,\ y)$, - $(d,\ \tfrac{3d}{2},\ 2d,\ y)$ when $d$ is even.
    743 
    744 **Step 3: parameters $(t,d)$ and then $(q,k)$.**
    745 
    746 It is convenient to measure the remaining room under $y$:
    747 
    748 $ t = y-2d. $
    749 
    750 Then the game state is represented by $(t,d)$.
    751 
    752 Write
    753 
    754 $ d = 2^k\cdot D,\qquad D\ \text{odd}, $
    755 
    756 and define
    757 
    758 $ q=\left\lfloor\frac{t}{D}\right\rfloor. $
    759 
    760 After this, the game depends only on $(q,k)$. We denote its Grundy number by $g(q,k)$.
    761 
    762 **Step 4: large ranges collapse to a few ranges of $q$.**
    763 
    764 In a fixed series, $d$ is fixed, hence $k$ and $D$ are fixed. As $x$ runs through $[l_i,r_i]$, the value $t=x-c_i$ runs through an interval $[L,R]$ where $L=l_i-c_i$ and $R=r_i-c_i$, and we look at
    765 
    766 $ q=\left\lfloor\frac{t}{D}\right\rfloor. $
    767 
    768 This $q$ stays constant on blocks of consecutive $D$ values, and the full blocks have length $D$. Since $D$ is odd, the contribution of the whole interval $t\in[L,R]$ can be reduced to:
    769 
    770 * one consecutive interval of $q$ values corresponding to full blocks,
    771 * at most two boundary blocks (the beginning and the end), treated separately.
    772 
    773 **Step 5: recursion for $g(q,k)$.**
    774 
    775 From the move description on $(q,k)$, we can write
    776 
    777 $ g(q,k)=\mathrm{mex}\Big(g(q-2^k,k),\ g(q,k-1),\ g(q-2^{k+1},k+1)\Big). $
    778 
    779 Two facts make it easy to work with:
    780 
    781 * the third term is never needed, so $g(q,k)=\mathrm{mex}\Big(g(q-2^k,k),\ g(q,k-1)\Big)$.
    782 * for fixed $k$, the sequence $g(0,k),g(1,k),\ldots$ is periodic with period $2^{k+1}$.
    783 
    784 Using the first fact, we get a simple split:
    785 
    786 * if $q \lt 2^k$, then $g(q-2^k,k)$ does not exist, so $g(q,k)=\mathrm{mex}\Big({g(q,k-1)}\Big)$.
    787 * if $q\ge 2^k$, then $g(q,k)=\mathrm{mex}\Big({g(q,k-1),\ g(q-2^k,k)}\Big)$.
    788 
    789 **Step 6: reduce interval XOR to prefix XOR.**
    790 
    791 In each series we need
    792 
    793 $ g(L,k)\oplus g(L+1,k)\oplus \cdots \oplus g(R,k). $
    794 
    795 Define the prefix XOR
    796 
    797 $ f(u,k)=g(0,k)\oplus g(1,k)\oplus \cdots \oplus g(u,k). $
    798 
    799 Then
    800 
    801 $ g(l,k)\oplus \cdots \oplus g(r,k)=f(r,k)\oplus f(l-1,k). $
    802 
    803 **Step 7: compute $f(u,k)$ as a small tuple.**
    804 
    805 We save $f(u,k)$ as a tuple
    806 
    807 $ (p_0,p_1,p_2), $
    808 
    809 where $p_i=1$ means the value $i$ has an odd contribution in
    810 
    811 $ f(u,k)=g(0,k)\oplus g(1,k)\oplus \cdots \oplus g(u,k). $
    812 
    813 In other words, $p_i$ tells whether $i$ appears an odd number of times among $g(0,k),\ldots,g(u,k)$.
    814 
    815 We first precompute the XOR over one full period
    816 
    817 $ f(2^{k+1}-1,k). $
    818 
    819 Since the period is $2^{k+1}$, two full consecutive periods cancel in XOR, so the XOR over length $2^{k+2}$ becomes $(0,0,0)$. Therefore, for a general $u$ we reduce it to the remainder inside a single period, and then compute it by recursion on $k$ from the formulas in Step 5. This makes computing $f(u,k)$ fast, in $O(k)=O(\log u)$ time.
    820 
    821 **Implementation**
    822 
    823 ```
    824 // In the name of God
    825 #include <iostream>
    826 using namespace std;
    827 #pragma GCC optimize("O3,unroll-loops,no-stack-protector")
    828 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    829 typedef long long ll;
    830  
    831 inline ll lg2(ll x){return 63 - __builtin_clzll(x);}
    832 constexpr inline ll period(ll k) {return 1LL<<(k+1);}
    833 constexpr inline ll half_period(ll k) {return 1LL<<k;}
    834 inline ll equivalent(ll x, ll k) {return x & (period(k)-1);}
    835 inline bool count_period_parity(ll x, ll k) {return (x >> (k+1)) & 1;}
    836  
    837 struct node {
    838     int u;
    839     node(bool zero, bool one, bool two) {
    840         u = ((int) zero << 0) + ((int) one << 1) + ((int) two << 2);
    841     }
    842     node(int x) {
    843         u = x;
    844     }
    845     bool has(int i) const {return u & (1<<i);}
    846     node Mex() const {
    847         return node(has(1) ^ has(2), has(0), false);
    848     }
    849     node MexMex() const {
    850         return node(false, has(2), has(0) ^ has(1));
    851     }
    852     node operator^(const node other) const {
    853         return node(u ^ other.u);
    854     }
    855     void operator^=(const node other) {
    856         u ^= other.u;
    857     }
    858     int get() const {
    859         return (u >> 1);
    860     }
    861 };
    862  
    863 const node full_period(true, true, false);
    864 const node full_period_mex = full_period.Mex();
    865 const node zero_node(false, false, false);
    866 const node zero(true, false, false), one(false, true, false), two(false, false, true);
    867  
    868 node grundy(ll x, ll k) {
    869     if(k)
    870         return equivalent(x, k) < half_period(k)? grundy(x, k-1).Mex() : grundy(x, k-1).MexMex();
    871     return x&1? one : zero;
    872 }
    873  
    874 node prefix_grundy(ll r, ll k) {
    875     node period_effect = (count_period_parity(r, k)? full_period : zero_node);
    876     r = equivalent(r, k);
    877     if(k == 0)
    878         return (r? full_period : zero) ^ period_effect;
    879     if(r < half_period(k))
    880         return prefix_grundy(r, k-1).Mex() ^ period_effect;
    881     return prefix_grundy(r - half_period(k), k-1).MexMex() ^ full_period_mex ^ period_effect;
    882 }
    883  
    884 inline node grundy(ll l, ll r, ll k) {
    885     return (l? prefix_grundy(l-1, k) : zero_node) ^ prefix_grundy(r, k);
    886 }
    887  
    888 int main() {
    889     ios_base::sync_with_stdio(false), cin.tie(nullptr);
    890     int n;
    891     int t;
    892     cin >> t;
    893     while(t--) {
    894         cin >> n;
    895         node ans(0);
    896         for(ll a, b, c, l, r, lp, rp, d, k, i = 0; i < n; i++) {
    897             cin >> a >> b >> c >> l >> r;
    898             b -= a, c -= a, l -= a, r -= a, a = 0;
    899             l -= c, r -= c;
    900             k = lg2(b & -b), d = b >> k;
    901             if(l / d == r / d) {
    902                 if((r - l + 1) & 1)
    903                     ans ^= grundy(l / d, k);
    904             } else {
    905                 lp = (l+d-1) / d, rp = r / d;
    906                 if(lp < rp) ans ^= grundy(lp, rp-1, k);
    907                 if((lp*d-l)&1) ans ^= grundy(l / d, k);
    908                 if((r-rp*d+1)&1) ans ^= grundy(r / d, k);
    909             }
    910         }
    911         cout << (ans.get()? "Bug" : "Feature") << '\n';
    912     }
    913     return 0;
    914 }
    915 // Thank God
    916 ```
    917 
    918 #### [2180H2 - Bug Is Feature (Conditional Version)](/contest/2180/problem/H2)
    919 
    920 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM"), [Shayan](/profile/Shayan "International Grandmaster Shayan") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
    921 
    922 **Solution**
    923 
    924 **Step 1: Game Transformation.**
    925 
    926 Convert each game with $a_i \lt b_i \lt c_i \le x$ to analyze $0 \lt 1 \lt 2 \le x'$ where:
    927 
    928 $x' = \left\lfloor \frac{x - a_i}{d_i} \right\rfloor, \quad d_i = b_i - a_i$
    929 
    930 The interval $[l_i, r_i]$ transforms to
    931 
    932 $[L_i, R_i] = \left[\left\lfloor \frac{l_i - a_i}{d_i} \right\rfloor, \left\lfloor \frac{r_i - a_i}{d_i} \right\rfloor\right].$
    933 
    934 Note that each $x' \in [L_i, R_i]$ corresponds to multiple original $x$ values (the number of originals can change near the interval endpoints). From state $x'$, a player can move either to $x'-1$ or to $\left\lfloor \frac{x'}{2} \right\rfloor$. The game ends when $x'=2$, and the player who makes the last move wins.
    935 
    936 **Step 2: Grundy Numbers.**
    937 
    938 Define $g(x)$ for state $0 \lt 1 \lt 2 \le x$:
    939 
    940 * Base cases:
    941 
    942 $g(2) = 0, \quad g(3) = 1$
    943 
    944 * Recursive rule ($x \ge 4$):
    945 
    946 $g(x) = \mathrm{MEX}\left(g(x-1), \ g\left(\left\lfloor \frac{x}{2} \right\rfloor\right)\right)$
    947 
    948 * Key properties (proven by induction):
    949 
    950   + $g(x) = 0$ $\iff$ $x$ has **odd trailing zeros** in binary
    951   + Non-zero $g(x)$ alternate $1 \leftrightarrow 2$ sequentially
    952 
    953 **Step 3: Counting Grundy Values.**
    954 
    955 For any interval $[l, r]$:
    956 
    957 * Count numbers with $g(x) = 0$:
    958 
    959   + Define $C(y) =$ count of ${x \le y \mid g(x) = 0}$
    960   + Loop through bits to compute $C(y)$ in $O(\log y)$
    961   + Zeros in $[l, r]$: $C(r) - C(l-1)$
    962 * Count $1$'s and $2$'s similarly using $C(y)$ and alternation of $1$ and $2$.
    963 
    964 **Step 4: Final Computation.**
    965 
    966 For each transformed interval $[L_i, R_i]$:
    967 
    968 * Compute XOR of all $g(x)$ in $[L_i, R_i]$
    969 * Aggregate XOR across all $n$ queries
    970 * Total XOR $\neq 0 \implies$ Bug wins; else Feature wins
    971 
    972 **Implementation**
    973 
    974 ```
    975 // In the name of God
    976 #include <iostream>
    977 using namespace std;
    978 typedef long long ll;
    979  
    980 inline ll count_zeros(ll x) {
    981     int u = (x&2)>>1;
    982     ll cnt = u;
    983     while (x>>=2) {
    984         u = (x&2)>>1;
    985         cnt += x+u;
    986     }
    987     return cnt;
    988 }
    989  
    990 // normal grundy function
    991 /*
    992 inline int grundy(ll x) {
    993     if((__builtin_ctzll(x)&1) == 1) return 0;
    994     return 1+((x-count_zeros(x))&1);
    995 }
    996 */
    997  
    998 // magical function
    999 inline int grundy(ll x) {
   1000     if((__builtin_ctzll(x)&1) == 1) return 0;
   1001     return 1+(__builtin_popcountll(x)&1);
   1002 }
   1003  
   1004 inline int grundy(ll l, ll r) {
   1005     ll zel = count_zeros(l-1), zer = count_zeros(r);
   1006     ll onl = (l-1-zel)/2, onr = (r-zer)/2;
   1007     ll twl = (l-2-zel)/2, twr = (r-1-zer)/2;
   1008     return ((onr-onl)&1)^(((twr-twl)&1)<<1);
   1009 }
   1010  
   1011 int main() {
   1012     ios_base::sync_with_stdio(false), cin.tie(0);
   1013     int n, ans;
   1014     int t;
   1015     cin >> t;
   1016     while(t--) {
   1017         cin >> n;
   1018         ans = 0;
   1019         for(ll a, b, c, l, r, lp, rp, i = 0; i < n; i++) {
   1020             cin >> a >> b >> c >> l >> r;
   1021             b -= a, c -= a, l -= a, r -= a, a = 0;
   1022             if(l / b == r / b) {
   1023                 if((r - l + 1)&1)
   1024                     ans ^= grundy(l / b);
   1025             } else {
   1026                 lp = (l+b-1)/b, rp = r/b;
   1027                 if(b&1) ans ^= grundy(lp, rp-1);
   1028                 if((lp*b-l)&1)ans ^= grundy(l/b);
   1029                 if((r-rp*b+1)&1)ans ^= grundy(rp);
   1030             }
   1031         }
   1032         cout << (ans?"Bug":"Feature") << '\n';
   1033     }
   1034     return 0;
   1035 }
   1036 ```