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