codeforces-scrape

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

1930.md (52546B)


      1 Source: https://codeforces.com/blog/entry/126043
      2 
      3 Thank you for your participation! I hope you liked atleast one problem from the set (:
      4 
      5 [1930A - Maximise The Score](/contest/1930/problem/A "think-cell Round 1")
      6 
      7 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
      8 Editorial: [Non-origination](/profile/Non-origination "Expert Non-origination")
      9 
     10 **Hint 1**
     11 
     12 Selecting the smallest two elements on the whiteboard is a good choice in the first move.
     13 
     14 **Solution**
     15 
     16 Let $b$ denote the sorted array $a$. Assume that $b$ contains only distinct elements for convenience. We prove by induction on $n$ that the maximum final score is $b_1 + b_3 + \ldots + b_{2n-1}$.
     17 
     18 For the base case $n = 1$, the final and only possible score that can be achieved is $b_1$.
     19 
     20 Now let $n \gt 1$.
     21 
     22 **Claim**: It is optimal to choose $b_{1}$ with $b_{2}$ for some move.
     23 
     24 **Proof**
     25 
     26 Suppose that in some move, $b_{1}$ is choosen with $b_i$ and $b_{2}$ is choosen with $b_j$, for some $2 \lt i,j \lt 2n, i \not = j$.
     27 
     28 The contribution to the score according to these choices is $\min(b_{1}, b_{i}) + \min(b_{2}, b_{j}) = b_{1} + b_{2}$.
     29 
     30 However, if we had chosen $b_{1}$ and $b_{2}$ in one move, and $b_i$ and $b_j$ in the other move, the score according to these choices is $\min(b_{1}, b_{2}) + \min(b_{i}, b_{j}) = b_{1} + \min(b_{i}, b_{j})$.
     31 
     32 As $i, j \gt 2$, $b_i \gt b_{2}$ and $b_j \gt b_{2} \implies \min(b_{i}, b_{j}) \gt b_2$. Thus, we can achieve a strictly larger score by choosing $b_1$ with $b_2$ in some move.
     33 
     34 The choice of selecting $b_1$ and $b_2$ contributes a value of $b_1$ to the score. The maximum score that can achieved for the remaining numbers $[b_3, b_4, \ldots, b_{2n}]$ on the whiteboard in the remaining moves is $b_3 + b_5 + b_7 + \ldots b_{2n-1}$ by the induction hypothesis.
     35 
     36 Note that we can extend the arguments for the case where $a$ has duplicate elements.
     37 
     38 **Code**
     39 
     40 ```
     41 #include <bits/stdc++.h>     
     42 using namespace std;
     43 #define ll long long
     44 void solve(){ 
     45     ll n; cin>>n;
     46     vector<ll> a(2*n);
     47     ll ans=0;
     48     for(auto &it:a){
     49         cin>>it;
     50     }
     51     sort(a.begin(),a.end());
     52     for(ll i=0;i<2*n;i+=2){
     53         ans+=a[i];
     54     }
     55     cout<<ans<<"\n";
     56     return;  
     57 }                                       
     58 int main()                                                                               
     59 {       
     60     ios_base::sync_with_stdio(false);                         
     61     cin.tie(NULL);                               
     62     #ifndef ONLINE_JUDGE                   
     63     freopen("input.txt", "r", stdin);                                           
     64     freopen("output.txt", "w", stdout);      
     65     freopen("error.txt", "w", stderr);                        
     66     #endif     
     67     ll test_cases=1;                 
     68     cin>>test_cases;
     69     while(test_cases--){
     70         solve();
     71     }
     72     cout<<fixed<<setprecision(10);
     73     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
     74 }
     75 ```
     76 
     77 [video editorial by aryanc403](https://youtu.be/OJdMGnC7SHM)
     78 
     79 [1930B - Permutation Printing](/contest/1930/problem/B "think-cell Round 1")
     80 
     81 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
     82 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
     83 
     84 **Hint 1**
     85 
     86 For integers $x$ ($\lfloor \frac{n}{2} \rfloor \lt x \leq n$), there does not exist integer $y$ ($y \gt x$) such that $y$ is divisible by $x$.
     87 
     88 **Solution**
     89 
     90 Consider the permutation $p$ such that $p=[1, n, 2, n - 1, \ldots \lceil \frac{n+1}{2} \rceil]$. It is valid. Why?
     91 
     92 **Proof**
     93 
     94 We have $\max(p_a, p_{a+1}) \gt \lfloor \frac{n}{2} \rfloor$ for all $1 \leq a \lt n - 1$. So we cannot ever have a pair of integers ($a,b$) such that:
     95 
     96 * $1 \leq a \lt n - 1$
     97 * $1 \leq b \lt n$
     98 * $a \neq b$
     99 * $p_a$ divides $p_b$ and $p_{a+1}$ divides $p_{b+1}$
    100 
    101 Now, we just need to check for $a = n - 1$. First of all, notice that $p_a$ does not divide $p_1$.
    102 
    103 There does not exist an integer $b$ ($2 \leq b \lt n - 1$) such that $p_{a+1}$ divides $p_{b+1}$ as $2 \cdot p_{a+1} \ge n$ and $p_{c+1} \lt n$ for all $c$ ($2 \leq c \lt n - 1$).
    104 
    105 Note that we covered all possible pairs of indices and did not find two **distinct** indices $i$ and $j$ ($1 \leq i, j \lt n$; $i \neq j$) such that $p_i$ divides $p_j$ and $p_{i+1}$ divides $p_{j+1}$.
    106 
    107 **Code**
    108 
    109 ```
    110 #include <bits/stdc++.h>     
    111 using namespace std;
    112 #define ll long long
    113 void solve(){ 
    114     ll n; cin>>n;
    115     ll l=1,r=n;
    116     for(ll i=1;i<=n;i++){
    117         if(i&1){
    118             cout<<l<<" ";
    119             l++;
    120         }
    121         else{
    122             cout<<r<<" ";
    123             r--;
    124         }
    125     }
    126     cout<<"\n";
    127     return;  
    128 }                                       
    129 int main()                                                                               
    130 {       
    131     ios_base::sync_with_stdio(false);                         
    132     cin.tie(NULL);                               
    133     #ifndef ONLINE_JUDGE                   
    134     freopen("input.txt", "r", stdin);                                           
    135     freopen("output.txt", "w", stdout);      
    136     freopen("error.txt", "w", stderr);                        
    137     #endif     
    138     ll test_cases=1;                 
    139     cin>>test_cases;
    140     while(test_cases--){
    141         solve();
    142     }
    143     cout<<fixed<<setprecision(10);
    144     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    145 }
    146 ```
    147 
    148 [video editorial by aryanc403](https://youtu.be/woPPBKBkCFk)
    149 
    150 [1930C - Lexicographically Largest](/contest/1930/problem/C "think-cell Round 1")
    151 
    152 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    153 Editorial: [Non-origination](/profile/Non-origination "Expert Non-origination") and [satyam343](/profile/satyam343 "Master satyam343")
    154 
    155 **Hint 1**
    156 
    157 Consider an array $c$ of length $n$ such that $c_i :=$ *number of indices smaller than $i$ which were chosen before index $i$*.
    158 
    159 So set $S$ will be a collection of $a_i + i - c_i$ over all $1 \leq i \leq n$.
    160 
    161 **Solution**
    162 
    163 Now one might wonder what type of arrays $c$ is it possible to get.
    164 
    165 First, it is easy to see that we should have $0 \leq c_i \lt i$ for all $i$. Call an array $c$ of length $n$ *good*, if $0 \leq c_i \lt i$ for all $1 \leq i \leq n$. The claim is that all *good* arrays of length $n$ can be obtained.
    166 
    167 **Proof**
    168 
    169 We can prove it by induction on $n$.
    170 
    171 $c_1 = 0$ always holds. Now $c_2$ can either be $0$ or $1$. We can obtain $c_2 = 0$ by deleting the element at index $2$ before the element at index $1$. We can also obtain $c_2 = 1$ by deleting it after deleting the element at index $1$. Thus, all *good* arrays of length 2 can be obtained.
    172 
    173 Now assume that it is possible to obtain all *good* arrays of length atmost $k$. Choose an integer $x$ ($0 \leq x \leq k$) arbitrarily. Consider the following sequence for the order of deletion:
    174 
    175 * The elements at indices $1, 2, \ldots, x$ in the same order.
    176 * The element at index $k$.
    177 * The elements at indices $x + 1, \ldots, k - 1$ in the same order.
    178 
    179 It is easy to see that the array obtained on performing the above sequence of operations is a *good* array of length $k + 1$ with $c_{k+1} = x$. Hence we can establish a bijection between the sequence of order of deletion and the number of *good* arrays.
    180 
    181 So we have the following subproblem. We have a set $S$. We will iterate $i$ from $1$ to $n$, select an integer $c_i$ ($0 \leq c_i \leq i - 1$) and insert $a_i + i - c_i$ into set $S$ and move to $i + 1$. Now using exchange arguments, we can prove that it is never bad if we select the smallest integer $v$ ($0 \leq v \leq i - 1$) such that $a_i + i - v$ is not present in the set $S$, and assign it to $c_i$. Note that as we have $i$ options for $v$, and we would have inserted exactly $i-1$ elements before index $i$, there always exists an integer $v$ ($0 \leq v \leq i - 1$) such that $a_i + i - v$ is not present in the set $S$. You can refer to the attached submission to see how to find $v$ efficiently for each $i$.
    182 
    183 **Code**
    184 
    185 ```
    186 #include <bits/stdc++.h>     
    187 using namespace std;
    188 #define ll long long
    189 void solve(){ 
    190     ll n; cin>>n;
    191     set<ll> used,not_used;
    192     vector<ll> ans;
    193     for(ll i=1;i<=n;i++){
    194         ll x; cin>>x; x+=i;
    195         if(!used.count(x)){
    196             not_used.insert(x);
    197         }
    198         ll cur=*(--not_used.upper_bound(x)); //find the largest element(<= x) which is not in set "used"
    199         not_used.erase(cur);
    200         ans.push_back(cur);
    201         used.insert(cur);
    202         if(!used.count(cur-1)){
    203             not_used.insert(cur-1);
    204         }
    205     }
    206     sort(ans.begin(), ans.end());
    207     reverse(ans.begin(), ans.end());
    208     for(auto i:ans){
    209         cout<<i<<" ";
    210     }  
    211     cout<<"\n";
    212     return;  
    213 }                                       
    214 int main()                                                                               
    215 {       
    216     ios_base::sync_with_stdio(false);                         
    217     cin.tie(NULL);                               
    218     #ifndef ONLINE_JUDGE                   
    219     freopen("input.txt", "r", stdin);                                           
    220     freopen("output.txt", "w", stdout);      
    221     freopen("error.txt", "w", stderr);                        
    222     #endif     
    223     ll test_cases=1;                 
    224     cin>>test_cases;
    225     while(test_cases--){
    226         solve();
    227     }
    228     cout<<fixed<<setprecision(10);
    229     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    230 }
    231 ```
    232 
    233 [video editorial by aryanc403](https://youtu.be/d8_f4ae0lJ8)
    234 
    235 [1930D1 - Sum over all Substrings (Easy Version)](/contest/1930/problem/D1 "think-cell Round 1")
    236 
    237 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    238 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
    239 
    240 **Hint 1**
    241 
    242 To find $f(s)$, we can partition $s$ into multiple independent substrings of length atmost $3$ and find best answer for them separately.
    243 
    244 **Hint 2**
    245 
    246 There always exists a string $g$ such that:
    247 
    248 1. $g$ is $s-good$
    249 2. there are $f(s)$ number of $\mathtt{1} $s in $g$
    250 3. $g$ is of the form $b_1 + b_2 + \ldots b_q$, where $b_i$ is either equal to $\mathtt{0}$ or $\mathtt{010}$.
    251 
    252 **Solution**
    253 
    254 First of all, append $n$ $\mathtt{0} $ s to the back of $s$ for our convenience. Note that this does not change the answer.
    255 
    256 Now let us call a binary string $p$ of size $d$ *nice* if:
    257 
    258 1. there exists a positive integer $k$ such that $d = 3k$
    259 2. $p$ is of form $ f(\mathtt{0} , k) + f(\mathtt{1} , k) + f(\mathtt{0} , k) $, where $f(c, z)$ gives a string containing exactly $z$ characters equal to $c$.
    260 
    261 Suppose binary string $t$ is one of the $s-good$ strings such that there are exactly $f(s)$ $\mathtt{1} $ s in $t$.
    262 
    263 We claim that for any valid $t$, there always exists a binary string $t'$ such that:
    264 
    265 1. $t'$ is permutation of $t$
    266 2. $t'$ is $s-good$
    267 3. $t'$ is of the form $f(\mathtt{0}, d_1) + z_1 + f(\mathtt{0}, d_2) + z_2 + f(\mathtt{0}, d_3) + \ldots + z_g + f(\mathtt{0}, d_{g+1}) $, where $z_1, z_2, \ldots z_g$ are *nice* binary strings and $d_1, d_2, \ldots d_{g+1}$ are non-negative integers.
    268 
    269 **Proof**
    270 
    271 Initially, all the $\mathtt{1} $s in $s$ are unmarked. We will mark all of them and modify the string $t$ in the process.
    272 
    273 We will do the following recursive process unless all the $\mathtt{1} $ s in $s$ are marked.
    274 
    275 Find the index of leftmost unmarked $\mathtt{1} $ in $s$. Suppose its index is $x$. Now suppose $y$ is the largest index such that there are an equal number of $\mathtt{0} $ s and $\mathtt{1} $ s in substring $t[x, y]$. Note that $y$ will always exist as we appended some extra $\mathtt{0} $s in the starting. Now we can rearrange the characters in substring $t[x,y]$, as they will still contain an equal number of $\mathtt{0} $ s and $\mathtt{1} $ s and $\mathtt{1} $ will still be the mode of substring $t[x,y]$. Obviously rearranging the characters in $t[x,y]$ to $\mathtt{0} \ldots \mathtt{0} \mathtt{1} \ldots \mathtt{1}$ is the best we can do. We will mark all the $\mathtt{1} $ s in substring $s[x,y]$. Suppose $y-x+1 = 2v$. Now $t[y+1,y+v]$ might contain some $\mathtt{1} $ s. Say there are $z$ $\mathtt{1} $ s in $t[y+1,y+v]$ initially. We will do the following operation exactly $z$ times.
    276 
    277 * Find the leftmost $\mathtt{1} $ in substring $t[y+1,y+v]$. Find the leftmost $\mathtt{0} $ in substring $t[y+v+1,2n]$. Swap both characters.
    278 
    279 Now note that $t[x,x+3v-1]$ will be of form $f(\mathtt{0}, v) + f(\mathtt{1}, v) + f(\mathtt{0}, v)$. It is easy to verify that in the updated $t$, there won't be any index $i$ for which there does not exist two indices $1 \le l \le i \le r \le 2n$ such that $s_i$ is *mode* of $t[l,r]$.
    280 
    281 Now we can mark all the $\mathtt{1} $ s in substring $s[x+2v,x+3v-1]$ too, as $t[x+v,x+3v-1]$ contain equal number of $\mathtt{0} $ s and $\mathtt{1} $ s.
    282 
    283 It is not hard to conclude that the updated $t$ will be of form $f(\mathtt{0}, d_1) + z_1 + f(\mathtt{0}, d_2) + z_2 + f(\mathtt{0}, d_3) + \ldots + z_g + f(\mathtt{0}, d_{g+1}) $, where $z_1, z_2, \ldots z_g$ are *nice* binary strings and $d_1, d_2, \ldots d_{g+1}$ are non-negative integers.
    284 
    285 Note that the $\mathtt{1}$ s in $t[x, x + 3v - 1]$ won't help the $\mathtt{1}$ s in $s[x + 3v, 2n]$. So, we can solve for $s[x + 3v, 2n]$ independently.
    286 
    287 Let $t'$ be the updated $t$.
    288 
    289 Now, carefully observe the structure of $t'$. We can replace all the substrings of the form $ f(\mathtt{0} , k) + f(\mathtt{1} , k) + f(\mathtt{0} , k) $ in $t'$ with $ \mathtt{0} \mathtt{1} \mathtt{0} \mathtt{0} \mathtt{1} \mathtt{0} \ldots \mathtt{0} \mathtt{1} \mathtt{0} \mathtt{0} \mathtt{1} \mathtt{0}$.
    290 
    291 So the updated $t'$(say $t"$) will be of form $b_1 + b_2 + \ldots b_q$, where $b_i$ is either equal to $\mathtt{0}$ or $\mathtt{010}$.
    292 
    293 So whenever we need to find $f(e)$ for some binary string $e$, we can always try to find a string of form $t"$ using as few $\mathtt{1} $s as possible. Notice that we can construct $t"$ greedily. You can look at the attached code for the implementation details. Also, we don't need to actually append the $\mathtt{0} $s at the back of $s$. It was just for proof purposes.
    294 
    295 **Code**
    296 
    297 ```
    298 #include <bits/stdc++.h>   
    299 #include <ext/pb_ds/tree_policy.hpp>
    300 #include <ext/pb_ds/assoc_container.hpp>
    301 using namespace __gnu_pbds;   
    302 using namespace std;
    303 #define ll long long
    304 #define pb push_back                  
    305 #define mp make_pair          
    306 #define nline "\n"                            
    307 #define f first                                            
    308 #define s second                                             
    309 #define pll pair<ll,ll> 
    310 #define all(x) x.begin(),x.end()     
    311 const ll MOD=1e9+7;
    312 const ll MAX=500500;
    313 ll f(string s){
    314     ll len=s.size(),ans=0,pos=0;
    315     while(pos<len){
    316         if(s[pos]=='1'){
    317             ans++;
    318             pos+=2;
    319         }
    320         pos++;
    321     }
    322     return ans;
    323 }
    324 void solve(){ 
    325     ll n,ans=0; cin>>n;
    326     string s; cin>>s; 
    327     for(ll i=0;i<n;i++){
    328         string t; 
    329         for(ll j=i;j<n;j++){
    330             t.push_back(s[j]);
    331             ans+=f(t);
    332         }
    333     }
    334     cout<<ans<<nline;
    335     return;  
    336 }                                       
    337 int main()                                                                               
    338 {     
    339     ios_base::sync_with_stdio(false);                         
    340     cin.tie(NULL);                               
    341     #ifndef ONLINE_JUDGE                 
    342     freopen("input.txt", "r", stdin);                                           
    343     freopen("output.txt", "w", stdout);      
    344     freopen("error.txt", "w", stderr);                        
    345     #endif     
    346     ll test_cases=1;                 
    347     cin>>test_cases;
    348     while(test_cases--){
    349         solve();
    350     }
    351     cout<<fixed<<setprecision(10);
    352     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    353 }
    354 ```
    355 
    356 [1930D2 - Sum over all Substrings (Hard Version)](/contest/1930/problem/D2 "think-cell Round 1")
    357 
    358 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    359 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
    360 
    361 **Hint 1**
    362 
    363 We can use the idea of D1 and dynamic programming to solve in $O(n)$.
    364 
    365 **Solution**
    366 
    367 Suppose $dp[i][j]$ denotes $f(s[i,j])$ for all $1 \le i \le j \le n$.
    368 
    369 Performing the transition is quite easy.
    370 
    371 If $s_i = \mathtt{1}$, $dp[i][j]=1+dp[i+3][j]$, otherwise $dp[i][j]=dp[i+1][j]$. Note that
    372 
    373 Unable to parse markup [type=CF_MATHJAX]
    374 
    375 for if $i \gt j$.
    376 
    377 So if we fix $j$, we can find $dp[i][j]$ for all $1 \le i \le j$ in $O(n)$, and the original problem in $O(n^2)$.
    378 
    379 Now, we need to optimise it.
    380 
    381 Suppose $track[i] = \sum_{j=i}^{n} dp[i][j]$ for all $1 \le i \le n$, with base condition that $track[i] = 0$ if $i \gt n$.
    382 
    383 There are two cases:
    384 
    385 * $s_i = \mathtt{0}$ :
    386 
    387 1. $track[i] = \sum_{j=i}^{n} dp[i][j]$
    388 2. $track[i] = dp[i][i] + \sum_{j=i+1}^{n} dp[i][j]$
    389 3. $track[i] = dp[i][i] + \sum_{j=i+1}^{n} dp[i+1][j]$
    390 4. $track[i] = track[i+1]$ as $dp[i][i]=0$
    391 
    392 * $s_i = \mathtt{1}$ :
    393 
    394 1. $track[i] = \sum_{j=i}^{n} dp[i][j]$
    395 2. $track[i] = \sum_{j=i}^{n} 1 + dp[i+3][j]$
    396 3. $track[i] = n - i + 1 + \sum_{j=i+3}^{n} dp[i+3][j]$ as $dp[i+3][i]=dp[i+3][i+1]=dp[i+3][i+2]=0$
    397 4. $track[i] = n - i + 1 + \sum_{j=i+3}^{n} dp[i+3][j]$
    398 5. $track[i] = n - i + 1 + track[i+3]$
    399 
    400 So, the answer to the original problem is $\sum_{i=1}^{n} track[i]$, which we can do in $O(n)$.
    401 
    402 **Code**
    403 
    404 ```
    405 #include <bits/stdc++.h>   
    406 #include <ext/pb_ds/tree_policy.hpp>
    407 #include <ext/pb_ds/assoc_container.hpp>
    408 using namespace __gnu_pbds;   
    409 using namespace std;
    410 #define ll long long
    411 #define pb push_back                  
    412 #define mp make_pair          
    413 #define nline "\n"                            
    414 #define f first                                            
    415 #define s second                                             
    416 #define pll pair<ll,ll> 
    417 #define all(x) x.begin(),x.end()     
    418 const ll MOD=1e9+7;
    419 const ll MAX=500500;
    420 void solve(){ 
    421     ll n,ans=0; cin>>n;
    422     string s; cin>>s; s=" "+s;
    423     vector<ll> dp(n+5,0);
    424     for(ll i=n;i>=1;i--){
    425         if(s[i]=='1'){
    426             dp[i]=dp[i+3]+n-i+1;
    427         }
    428         else{
    429             dp[i]=dp[i+1];
    430         }
    431         ans+=dp[i];
    432     }
    433     cout<<ans<<nline;
    434     return;  
    435 }                                       
    436 int main()                                                                               
    437 {     
    438     ios_base::sync_with_stdio(false);                         
    439     cin.tie(NULL);                               
    440     #ifndef ONLINE_JUDGE                 
    441     freopen("input.txt", "r", stdin);                                           
    442     freopen("output.txt", "w", stdout);      
    443     freopen("error.txt", "w", stderr);                        
    444     #endif     
    445     ll test_cases=1;                 
    446     cin>>test_cases;
    447     while(test_cases--){
    448         solve();
    449     }
    450     cout<<fixed<<setprecision(10);
    451     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    452 }
    453 ```
    454 
    455 [1930E - 2..3...4.... Wonderful! Wonderful!](/contest/1930/problem/E "think-cell Round 1")
    456 
    457 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    458 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
    459 
    460 **Hint 1**
    461 
    462 Suppose you are given some array $b$ of length $m$ and a positive integer $k$. How to check whether we can get the array $b$ if we start with an array $a$ of length $n$ such that $a_i = i$ for all $i$ ($1 \leq i \leq n$)?
    463 
    464 **Hint 2**
    465 
    466 First of all, array $b$ should be a subsequence of $a$. Now consider an increasing array $c$ (possibly empty) such that it contains all the elements of $a$ which are not present in $b$. Now look at some trivial necessary conditions.
    467 
    468 * The length of array $c$ should divisible by $2k$, as exactly $2k$ elements were deleted in one operation.
    469 * There should be atleast one element $v$ in $b$ such that there are atleast $k$ elements smaller than $v$ in the array $c$, and alteast $k$ elements greater than $v$ in the array $c$. Why? Think about the last operation. We can consider the case of empty $c$ separately.
    470 
    471 In fact, it turns out that these necessary conditions are sufficient (Why?).
    472 
    473 **Solution**
    474 
    475 Now, we need to find the number of possible $b$. We can instead find the number of binary strings $s$ of length $n$ such that $s_i = 1$ if $i$ is present in $b$, and $s_i=0$ otherwise.
    476 
    477 For given $n$ and $k$, let us call $s$ **good** if there exists some $b$ which can be achieved from $a$.
    478 
    479 Instead of counting strings $s$ which are **good**, let us count the number of strings which are not **good**.
    480 
    481 For convenience, we will only consider strings $s$ having the number of $\mathtt{0}$'s divisible by $2k$.
    482 
    483 Now, based on the conditions in hint $2$, we can conclude that $s$ is **bad** if and only if there does not exist any $1$ between the $k$-th $0$ from the left and the $k$-th $0$ from the right in $s$.
    484 
    485 Let us compress all the $\mathtt{0}$'s between the $k$-th $0$ from the left and the $k$-th $0$ from the right into a single $0$ and call the new string $t$. Note that $t$ will have exactly $2k - 1$ $\mathtt{0}$'s. We can also observe that for each $t$, a unique $s$ exists. This is only because we have already fixed the parameters $n$ and $k$. Thus the number of **bad** $s$ having exactly $x$ $\mathtt{1}$'s is ${{x + 2k - 1} \choose {2k - 1}}$ as there are exactly ${{x + 2k - 1} \choose {2k - 1}}$ binary strings $t$ having $2k - 1$ $\mathtt{0}$'s and $x$ $\mathtt{1}$'s.
    486 
    487 Finally, there are exactly $\binom{n}{x} - \binom{x + 2k - 1}{2k - 1}$ **good** binary strings $s$ having $x$ $\mathtt{1}$'s and $n-x$ $\mathtt{0}$'s. Now, do we need to find this value for each $x$ from $1$ to $n$? No, as the number($n-x$) of $\mathtt{0}$'s in $s$ should be a multiple of $2k$. There are only $O(\frac{n}{2k})$ useful candidates for $x$.
    488 
    489 Thus, our overall complexity is $O(n \log(n))$ (as $\sum_{i=1}^{n} O(\frac{n}{i}) = O(n \log(n))$).
    490 
    491 **Code**
    492 
    493 ```
    494 #pragma GCC optimize("O3,unroll-loops")
    495 #include <bits/stdc++.h>   
    496 #include <ext/pb_ds/tree_policy.hpp>
    497 #include <ext/pb_ds/assoc_container.hpp>
    498 using namespace __gnu_pbds;   
    499 using namespace std;
    500 #define ll long long
    501 const ll INF_ADD=1e18;
    502 #define pb push_back                  
    503 #define mp make_pair          
    504 #define nline "\n"                            
    505 #define f first                                            
    506 #define s second                                             
    507 #define pll pair<ll,ll> 
    508 #define all(x) x.begin(),x.end()     
    509 const ll MOD=998244353;
    510 const ll MAX=5000500;
    511 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
    512 ll binpow(ll a,ll b,ll MOD){
    513     ll ans=1;
    514     a%=MOD;  
    515     while(b){
    516         if(b&1)
    517             ans=(ans*a)%MOD;
    518         b/=2;
    519         a=(a*a)%MOD;
    520     }
    521     return ans;
    522 }
    523 ll inverse(ll a,ll MOD){
    524     return binpow(a,MOD-2,MOD);
    525 } 
    526 void precompute(ll MOD){
    527     for(ll i=2;i<MAX;i++){
    528         fact[i]=(fact[i-1]*i)%MOD;
    529     }
    530     inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    531     for(ll i=MAX-2;i>=0;i--){
    532         inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    533     }
    534 }
    535 ll nCr(ll a,ll b,ll MOD){
    536     if(a==b){
    537         return 1;
    538     }
    539     if((a<0)||(a<b)||(b<0))
    540         return 0;   
    541     ll denom=(inv_fact[b]*inv_fact[a-b])%MOD; 
    542     return (denom*fact[a])%MOD;    
    543 }
    544 ll n,k;    
    545 ll ways(ll gaps,ll options){
    546     gaps--;
    547     ll now=nCr(gaps+options-1,options-1,MOD);
    548     return now;
    549 }
    550 void solve(){
    551     cin>>n; 
    552     for(ll k=1;k<=(n-1)/2;k++){
    553         ll ans=1;
    554         for(ll deleted=2*k;deleted<=n-1;deleted+=2*k){
    555             ll options=2*k,left_elements=n-deleted;
    556             ans=(ans+ways(left_elements+1,deleted+1)-ways(left_elements+1,options)+MOD)%MOD;  
    557         }
    558         cout<<ans<<" ";
    559     }
    560     cout<<nline;
    561     return;   
    562 }                                       
    563 int main()                                                                               
    564 {     
    565     ios_base::sync_with_stdio(false);                         
    566     cin.tie(NULL); 
    567     #ifndef ONLINE_JUDGE                 
    568     freopen("input.txt", "r", stdin);                                           
    569     freopen("output.txt", "w", stdout);      
    570     freopen("error.txt", "w", stderr);                        
    571     #endif  
    572     ll test_cases=1;                 
    573     cin>>test_cases;
    574     precompute(MOD);
    575     while(test_cases--){
    576         solve();
    577     }
    578     cout<<fixed<<setprecision(10);
    579     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    580 }
    581 ```
    582 
    583 [1930F - Maximize the Difference](/contest/1930/problem/F "think-cell Round 1")
    584 
    585 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    586 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
    587 
    588 **Hint 1**
    589 
    590 Note that $\max - \min$ is just the difference of two elements, so let us first look at two numbers $y$ and $z$, where we want to maximise $(y | x) - (z | x)$. In $y - z$, the bits only present in $y$ add to the result, and the bits only present in $z$ reduce it. Setting a bit in $x$ puts it in both numbers, so that bit just stops mattering. Now, if we take $x = z$, we kill every bit that reduces the result without touching any bit that increases it, which is the best possible case.
    591 
    592 Now take an optimal $x$, and say $b_i | x$ is the maximum and $b_j | x$ is the minimum. Switching to $x = b_j$ can't make the difference of this pair smaller, and the range of the whole array is atleast this difference, so $x = b_j$ is optimal too. Note that other values of $x$ can also be optimal, but we can always get the maximum possible value by choosing $x = b_p$ for some $p$ $(1 \le p \le m)$.
    593 
    594 **Hint 2**
    595 
    596 In Hint 1, we saw that a single pair $(y, z)$ gets its best answer at $x = z$. Let us see why $f(b)$ is just the best answer among all pairs.
    597 
    598 It can't be more. Whatever $x$ we choose, $\max - \min$ is just the difference of the two elements that end up as the maximum and the minimum. That pair can't do better than its own best answer, so no $x$ can beat the best pair.
    599 
    600 And we can actually reach it. Take the best pair $(b_i, b_j)$ and choose $x = b_j$. By Hint 1, just these two elements already give this pair's best answer, and the other elements can only stretch $\max - \min$, never shrink it.
    601 
    602 Now, what is the answer for a pair? With $x = z$, the bits of $z$ cancel out, and we are left with exactly the bits present in $y$ but not in $z$. In other words, the answer is the maximum value $v$ such that $v \land y = v$ and $v \land z = 0$, which is $y \land {\sim} z$. Hence,
    603 
    604 $f(b) = \max_{1 \le i, j \le m} \left(b_i \land {\sim} b_j\right),$
    605 
    606 where $\land$ is the bitwise AND operator and ${\sim}$ is the bitwise One's complement operator.
    607 
    608 **Solution**
    609 
    610 Let us see how to find $f(b)$ in $O(n \log(n))$ first. We will focus on updates later. Let us have two sets $S_1$ and $S_2$ such that
    611 
    612 * $S_1$ contains all submasks of $b_i$ for all $1 \leq i \leq m$
    613 * $S_2$ contains all submasks of ~$b_i$for all $1 \leq i \leq m$
    614 
    615 We can observe that $f(b)$ is the largest element present in both sets $S_1$ and $S_2$.
    616 
    617 Now, we can insert all submasks naively. But it would be pretty inefficient. Note that we need to insert any submask atmost once in either of the sets.
    618 
    619 Can you think of some approach in which you efficiently insert all the non-visited submasks of some mask?
    620 
    621 **Pseudo Code**
    622 
    623 ```
    624 insert_submask(cur, S){
    625     return if mask cur is present in S
    626     add mask cur to the set S
    627     vec = list of all the set bits of the mask cur
    628     for i in vec:
    629         insert_submask(cur - 2^i)
    630 }
    631 ```
    632 
    633 Note that the above pseudo code inserts all the all submasks efficiently. As all the masks will be visited atmost once, the amortised complexity will be $O(n \log(n)^2)$. Note that instead of using a set, we can use a boolean array of size $n$ to reduce the complexity to $O(n \log(n))$.
    634 
    635 Thus, we can use the above idea to find $f(b)$ in $O(n \log(n))$. For each $i$ from $1$ to $m$, we can insert all submasks of $b_i$ into set $S_1$ and insert all the submasks of ~$b_i$ into set $S_2$.
    636 
    637 The above idea hints at how to deal with updates. If we need to append an element $z$ to $b$, we can just insert all submasks of $z$ into set $S_1$ and insert all the submasks of ~$z$ into set $S_2$.
    638 
    639 Hence, the overall complexity is $O(n \log(n))$.
    640 
    641 **Code**
    642 
    643 ```
    644 #pragma GCC optimize("O3,unroll-loops")
    645 #include <bits/stdc++.h>   
    646 #include <ext/pb_ds/tree_policy.hpp>
    647 #include <ext/pb_ds/assoc_container.hpp>
    648 using namespace __gnu_pbds;   
    649 using namespace std;
    650 #define ll long long
    651 #define pb push_back                  
    652 #define mp make_pair          
    653 #define nline "\n"                            
    654 #define f first                                            
    655 #define s second                                             
    656 #define pll pair<ll,ll> 
    657 #define all(x) x.begin(),x.end() 
    658 const ll MAX=100100; 
    659 void solve(){     
    660     ll n,q; cin>>n>>q;
    661     ll till=1,len=1;
    662     while(till<n){
    663         till*=2;
    664         len++;
    665     }
    666     ll ans=0;
    667     vector<vector<ll>> track(2,vector<ll>(till+5,0));
    668     auto add=[&](ll x,ll p){
    669         queue<ll> trav;
    670         if(track[p][x]){
    671             return;
    672         }
    673         trav.push(x); track[p][x]=1;
    674         while(!trav.empty()){
    675             auto it=trav.front();
    676             trav.pop();
    677             if(track[0][it]&track[1][it]){
    678                 ans=max(ans,it);
    679             }
    680             for(ll j=0;j<len;j++){
    681                 if(it&(1<<j)){
    682                     ll cur=(it^(1<<j));   
    683                     if(!track[p][cur]){
    684                         track[p][cur]=1;
    685                         trav.push(cur);
    686                     }
    687                 }
    688             }
    689         }
    690     };
    691     ll supermask=till-1;
    692     vector<ll> a(q+5);
    693     for(ll i=1;i<=q;i++){
    694         ll h; cin>>h; 
    695         a[i]=(h+ans)%n;
    696         add(a[i],0);
    697         add(supermask^a[i],1);
    698         cout<<ans<<" \n"[i==q];
    699     }
    700     return;  
    701 }                                         
    702 int main()                                                                               
    703 {     
    704     ios_base::sync_with_stdio(false);                         
    705     cin.tie(NULL);                               
    706     #ifndef ONLINE_JUDGE                 
    707     freopen("input.txt", "r", stdin);                                           
    708     freopen("output.txt", "w", stdout);      
    709     freopen("error.txt", "w", stderr);                        
    710     #endif     
    711     ll test_cases=1;                 
    712     cin>>test_cases;
    713     while(test_cases--){
    714         solve();
    715     }
    716     cout<<fixed<<setprecision(10);
    717     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    718 }
    719 ```
    720 
    721 [1930G - Prefix Max Set Counting](/contest/1930/problem/G "think-cell Round 1")
    722 
    723 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    724 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
    725 
    726 **Hint 1**
    727 
    728 Consider some subsequence $S$ of $[1,2, \ldots n]$ such that there exists atleast one pre-order $a$ such that $F(a)=S$. Look for some non-trivial properties about $S$. Node $S_i$ will be visited before the node $S_{i+1}$.
    729 
    730 **Hint 2**
    731 
    732 Assume $|S|=k$. First of all, we should $S_1=1$ and $S_k = n$. There cannot exists there distinct indices $a, b$ and $c$ ($1 \leq a \lt b \lt c \leq |k|$) such that $S_c$ lies on the path from $S_a$ to $S_b$. Assume $LCA_i$ is the lowest common ancestor of $S_i$ and $S_{i+1}$. For all $i$($1 \leq i \lt k$), the largest value over all the nodes on the unique path from $S_i$ to $S_{i+1}$ should be $S_{i+1}$.
    733 
    734 **Hint 3**
    735 
    736 Suppose $nax_p$ is the maximum value in the subtree of $p$. There is one more important restriction if $S_i$ does not lie on the path from $S_{i+1}$ to $1$. Suppose $m$ is the child of $LCA_i$, which lies on the path from $S_i$ to $LCA_i$. We should have $S_{i+1} \gt nax_m$. In fact, if you observe carefully you will realise that we should have $S_i = nax_m$.
    737 
    738 **Solution**
    739 
    740 Let us use dynamic programming. Suppose $dp[i]$ gives the number of valid subsequences(say $S$) such that the last element of $S$ is $i$. Note that the answer to our original problem will be $dp[n]$.
    741 
    742 Suppose $nax(u,v)$ denotes the maximum value on the path from $u$ to $v$(including the endpoints).
    743 
    744 Let us have a $O(n^2)$ solution first.
    745 
    746 We have $dp[1]=1$.
    747 
    748 Suppose we are at some node $i$($i \gt 1$), and we need to find $dp[i]$. Let us consider some node $j$($1 \le j \lt i$) and see if we can append $i$ to all the subsequences which end with node $j$. If we can append, we just need to add $dp[j]$ to $dp[i]$.
    749 
    750 But how do we check if we can append $i$ to all the subsequences that end with node $j$?
    751 
    752 Check hints 2 and 3.
    753 
    754 So, we have a $n^2$ solution now.
    755 
    756 We need to optimise it now.
    757 
    758 We will move in the increasing value of the nodes(from $2$ to $n$) and calculate the $dp$ values.
    759 
    760 Suppose $nax(1, par_i) = v$, where $par_i$ denotes the parent of $i$.
    761 
    762 Assume we go from node $j$($j \lt i$) to node $i$.
    763 
    764 There are two cases:
    765 
    766 1. $j$ lies on the path from $1$ to $i$: This case is easy, as we just need to ensure that $nax(j,par_i) = j$. We can add $dp[j]$ to $dp[i]$ if we have $nax(j,par_i) = j$. Note that there exists only one node(node $v$) for which might add $dp[v]$ to $dp[i]$
    767 2. $j$ does not lie on the path from $1$ to $i$ : We will only consider the case in which $dp[j]$ will be added to $dp[i]$. Suppose $lca$ is the lowest common ancestor of $j$ and $i$, and $m$ is the child of $lca$, which lies on the path from $j$ to $lca$. Notice that the largest value in the subtree of $m$ should be $j$. This observation is quite helpful. We can traverse over all the ancestors of $i$. Suppose that we are at ancestor $u$. We will iterate over all the child(say $c$) of $u$ such that $nax_c \lt i$, and add $dp[nax_c]$ to $dp[i]$ if $nax(u,par_i) \lt nax_c$. Suppose $track[u][i]$ stores the sum of $dp[nax_c]$ for all $c$ such that $nax_c \lt i$. So we should add $track[u][i]$ to $dp[i]$. But there is a catch. This way, $dp[nax_c]$ will also get added $dp[i]$ even when $nax_c \lt nax(u, par_i)$. So, we need to subtract some values, which is left as an exercise for the readers. Now, $track[u][d] = track[u][d-1] + dp[nax_c]$ if $nax_c = d$. So, instead of keeping a two-dimensional array $track$, we can just maintain a one-dimensional array $track$. Note that we will only need the sum of $track[u]$ for all the ancestors of $i$, which we can easily calculate using the euler tour.
    768 
    769 You can look at the attached code for the implementation details.
    770 
    771 The intended time complexity is $O(n \cdot \log(n))$.
    772 
    773 **Code**
    774 
    775 ```
    776 #include <bits/stdc++.h>   
    777 #include <ext/pb_ds/tree_policy.hpp>
    778 #include <ext/pb_ds/assoc_container.hpp>
    779 using namespace __gnu_pbds;   
    780 using namespace std;
    781 #define ll long long
    782 #define pb push_back                  
    783 #define mp make_pair          
    784 #define nline "\n"                            
    785 #define f first                                            
    786 #define s second                                             
    787 #define pll pair<ll,ll> 
    788 #define all(x) x.begin(),x.end()     
    789 const ll MOD=998244353;
    790 const ll MAX=1000100;
    791 struct FenwickTree{
    792     vector<ll> bit; 
    793     ll n;
    794     FenwickTree(ll n){
    795         this->n = n;
    796         bit.assign(n, 0);
    797     }
    798     FenwickTree(vector<ll> a):FenwickTree(a.size()){  
    799         ll x=a.size();
    800         for(size_t i=0;i<x;i++)
    801             add(i,a[i]);
    802     }
    803     ll sum(ll r) {
    804         ll ret=0;
    805         for(;r>=0;r=(r&(r+1))-1){
    806             ret+=bit[r];
    807             ret%=MOD;
    808         }
    809         return ret;
    810     }
    811     ll sum(ll l,ll r) {
    812         if(l>r)
    813             return 0;
    814         ll val=sum(r)-sum(l-1)+MOD;
    815         val%=MOD;
    816         return val;
    817     }
    818     void add(ll idx,ll delta) {
    819         for(;idx<n;idx=idx|(idx+1)){
    820             bit[idx]+=delta;
    821             bit[idx]%=MOD;
    822         }
    823     }
    824 };
    825 vector<vector<ll>> adj;
    826 vector<ll> tin(MAX,0),tout(MAX,0);
    827 vector<ll> parent(MAX,0);
    828 vector<ll> overall_max(MAX,0);
    829 ll now=1;
    830 vector<ll> jump_to(MAX,0),sub(MAX,0);
    831 void dfs(ll cur,ll par){
    832     parent[cur]=par;
    833     tin[cur]=now++;
    834     overall_max[cur]=cur;
    835     for(auto chld:adj[cur]){
    836         if(chld!=par){
    837             jump_to[chld]=max(jump_to[cur],cur);
    838             dfs(chld,cur);
    839             overall_max[cur]=max(overall_max[cur],overall_max[chld]);
    840         }
    841     }
    842     tout[cur]=now++;
    843 }
    844 vector<ll> dp(MAX,0);
    845 void solve(){ 
    846     ll n; cin>>n;
    847     adj.clear();
    848     adj.resize(n+5);
    849     for(ll i=1;i<=n-1;i++){
    850         ll u,v; cin>>u>>v;
    851         adj[u].push_back(v);  
    852         adj[v].push_back(u);
    853     }  
    854     now=1;      
    855     dfs(1,0);      
    856     ll ans=0;    
    857     FenwickTree enter_time(now+5),exit_time(now+5);
    858     overall_max[0]=MOD;   
    859     dp[0]=1;    
    860     for(ll i=1;i<=n;i++){
    861         ll p=jump_to[i];
    862         dp[i]=(enter_time.sum(0,tin[i])-exit_time.sum(0,tin[i])-sub[p]+dp[p]+MOD+MOD)%MOD;
    863         if(p>i){  
    864             dp[i]=0;
    865         }
    866         ll node=i;
    867         while(overall_max[node]==i){
    868             node=parent[node];
    869         }
    870         enter_time.add(tin[node],dp[i]);
    871         exit_time.add(tout[node],dp[i]);
    872         sub[i]=(enter_time.sum(0,tin[i])-exit_time.sum(0,tin[i])+MOD)%MOD;
    873     }
    874     cout<<dp[n]<<nline;
    875     return;  
    876 }                                       
    877 int main()                                                                               
    878 {       
    879     ios_base::sync_with_stdio(false);                         
    880     cin.tie(NULL);                               
    881     #ifndef ONLINE_JUDGE                 
    882     freopen("input.txt", "r", stdin);                                           
    883     freopen("output.txt", "w", stdout);      
    884     freopen("error.txt", "w", stderr);                        
    885     #endif     
    886     ll test_cases=1;                 
    887     cin>>test_cases;
    888     while(test_cases--){
    889         solve();
    890     }
    891     cout<<fixed<<setprecision(10);
    892     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    893 }
    894 ```
    895 
    896 [1930H - Interactive Mex Tree](/contest/1930/problem/H "think-cell Round 1")
    897 
    898 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
    899 Editorial: [satyam343](/profile/satyam343 "Master satyam343")
    900 
    901 **Hint 1**
    902 
    903 $\operatorname{MEX}$ of the path from $u$ to $v$ will be the minimum value over all the nodes of $T$ which do not lie on the path from $u$ to $v$.
    904 
    905 **Hint 2**
    906 
    907 $p_1$ and $p_2$ are associated with the Euler tour
    908 
    909 **Hint 3**
    910 
    911 $p_1$ is the permutation of $[1,2, \ldots n]$ sorted in increasing order on the basis on $tin$ time observed during Euler tour. Similarly, $p_2$ is the permutation of $[1,2, \ldots n]$ sorted in increasing order based on $tout$ time. Note that any Euler tour is fine.
    912 
    913 **Solution**
    914 
    915 Now we have $p_1$ and $p_2$ with us. Suppose we need to find $\operatorname{MEX}$ of the path from $u$ to $v$. Assume that $tin_u \lt tin_v$ for convenience. Assume $T'$ is the forest we get if we remove all the nodes on the path from $u$ to $v$ from $T$. Our goal is to find the minimum value over all the nodes in $T'$. Assume that $T'$ is non-empty, as $\operatorname{MEX}$ will be $n$ if $T'$ is empty. Assume $LCA$ is the lowest common ancestor of $u$ and $v$. Suppose $m$ is the child of $LCA(u,v)$, which lies on the path from $v$ to $LCA(u,v)$.
    916 
    917 Let us consider some groups of nodes $p$ such that.
    918 
    919 1. $tout_p \lt tin_u$
    920 2. $tin_u \lt tin_p \lt tin_m$
    921 3. $tin_m \lt tout_p \lt tin_v$
    922 4. $tin_v \lt tin_p$
    923 5. $tout_{LCA} \lt tout_p$
    924 
    925 Note that we have precisely $5$ groups, with the $i$-th group consisting of only those nodes which satisfy the $i$-th condition.
    926 
    927 Here comes the interesting claim. All nodes in $T'$ are present in atleast one of the above $5$ groups. There does not exist a node $p$ such that $p$ is on the path from $u$ from $v$ and $p$ is present in any of the groups.
    928 
    929 Now, it is not hard to observe that if we consider the nodes of any group, they will form a continuous segment in either $p_1$ or $p_2$. So we can cover each group in a single query. Hence, we can find the $\operatorname{MEX}$ of the path in any round using atmost $5$ queries.
    930 
    931 **Code**
    932 
    933 ```
    934 #include <bits/stdc++.h>   
    935 #include <ext/pb_ds/tree_policy.hpp>
    936 #include <ext/pb_ds/assoc_container.hpp>
    937 using namespace __gnu_pbds;   
    938 using namespace std;
    939 #define ll long long
    940 const ll INF_ADD=1e18;
    941 #define pb push_back                  
    942 #define mp make_pair          
    943 #define nline "\n"                            
    944 #define f first                                            
    945 #define s second                                             
    946 #define pll pair<ll,ll> 
    947 #define all(x) x.begin(),x.end()     
    948 const ll MOD=998244353;
    949 const ll MAX=200200;   
    950 vector<ll> adj[MAX];
    951 ll now=0,till=20;
    952 vector<ll> tin(MAX,0),tout(MAX,0),depth(MAX,0);
    953 vector<vector<ll>> jump(MAX,vector<ll>(till+1,0));
    954 void dfs(ll cur,ll par){
    955     jump[cur][0]=par;
    956     for(ll i=1;i<=till;i++)
    957         jump[cur][i]=jump[jump[cur][i-1]][i-1];
    958     tin[cur]=++now;
    959     for(ll chld:adj[cur]){
    960         if(chld!=par){
    961             depth[chld]=depth[cur]+1;
    962             dfs(chld,cur);
    963         }
    964     }
    965     tout[cur]=++now;
    966 } 
    967 bool is_ancestor(ll a,ll b){
    968     if((tin[a]<=tin[b])&&(tout[a]>=tout[b]))
    969         return 1;
    970     return 0;
    971 } 
    972 ll lca(ll a,ll b){
    973     if(is_ancestor(a,b))
    974         return a;
    975     for(ll i=till;i>=0;i--){
    976         if(!is_ancestor(jump[a][i],b))
    977             a=jump[a][i];
    978     }
    979     return jump[a][0];
    980 }  
    981 void solve(){
    982     ll n; cin>>n;
    983     ll m; cin>>m;
    984     vector<ll> a(n+5);
    985     for(ll i=1;i<=n-1;i++){
    986         ll u,v; cin>>u>>v;
    987         adj[u].push_back(v);
    988         adj[v].push_back(u);
    989     }
    990     now=1;
    991     dfs(1,1);
    992     vector<ll> p(n),q(n);
    993     for(ll i=0;i<n;i++){
    994         p[i]=q[i]=i+1;
    995     }
    996     sort(all(p),[&](ll l,ll r){
    997         return tin[l]<tin[r];
    998     });
    999     sort(all(q),[&](ll l,ll r){
   1000         return tout[l]<tout[r];
   1001     });
   1002     for(auto it:p){
   1003         cout<<it<<" ";
   1004     }
   1005     cout<<endl;
   1006     for(auto it:q){
   1007         cout<<it<<" ";
   1008     }
   1009     cout<<endl;
   1010     auto query_p=[&](ll l,ll r){
   1011         ll left_pos=n+1,right_pos=-1;
   1012         for(ll i=0;i<n;i++){
   1013             ll node=p[i];
   1014             if((tin[node]>=l) and (tin[node]<=r)){
   1015                 left_pos=min(left_pos,i);
   1016                 right_pos=i;
   1017             }
   1018         }
   1019         ll now=n+5;
   1020         if(right_pos!=-1){
   1021             left_pos++,right_pos++;
   1022             cout<<"? 1 "<<left_pos<<" "<<right_pos<<endl;
   1023             cin>>now;
   1024         }
   1025         return now;
   1026     };
   1027     auto query_q=[&](ll l,ll r){
   1028         ll left_pos=n+1,right_pos=-1;
   1029         for(ll i=0;i<n;i++){
   1030             ll node=q[i];
   1031             if((tout[node]>=l) and (tout[node]<=r)){
   1032                 left_pos=min(left_pos,i);
   1033                 right_pos=i;
   1034             }
   1035         }
   1036         ll now=n+5;
   1037         if(right_pos!=-1){
   1038             left_pos++,right_pos++;
   1039             cout<<"? 2 "<<left_pos<<" "<<right_pos<<endl;
   1040             cin>>now;
   1041         }
   1042         return now;
   1043     };
   1044     while(m--){
   1045         ll u,v; cin>>u>>v;
   1046         if(tout[u]>tout[v]){
   1047             swap(u,v);
   1048         }
   1049         ll lca_node=lca(u,v);
   1050         ll ans=n;
   1051         if(lca_node==v){
   1052             ans=min(ans,query_q(1,tin[u]));
   1053             ans=min(ans,query_p(tin[u]+1,tout[v]));
   1054             ans=min(ans,query_q(tout[v]+1,now));
   1055             cout<<"! "<<ans<<endl;
   1056             ll x; cin>>x;
   1057             continue;
   1058         }
   1059         ans=min(ans,query_q(1,tin[u]));
   1060         ll consider=v;
   1061         for(auto it:adj[lca_node]){
   1062             if(is_ancestor(lca_node,it) and is_ancestor(it,v)){
   1063                 consider=it;
   1064             }
   1065         }
   1066         ans=min(ans,query_p(tin[u]+1,tin[consider]-1));
   1067         ans=min(ans,query_q(tin[consider],tin[v]));
   1068         ans=min(ans,query_p(tin[v]+1,tout[lca_node]));
   1069         ans=min(ans,query_q(tout[lca_node]+1,now));
   1070         cout<<"! "<<ans<<endl;
   1071         ll x; cin>>x;
   1072     }
   1073     for(ll i=1;i<=n;i++){
   1074         adj[i].clear();
   1075     }
   1076     return;  
   1077 }                                       
   1078 int main()                                                                               
   1079 {     
   1080     ios_base::sync_with_stdio(false);                         
   1081     cin.tie(NULL); 
   1082     #ifndef ONLINE_JUDGE                 
   1083     freopen("input.txt", "r", stdin);                                           
   1084     freopen("output.txt", "w", stdout);      
   1085     freopen("error.txt", "w", stderr);                        
   1086     #endif  
   1087     ll test_cases=1;                 
   1088     cin>>test_cases;
   1089     while(test_cases--){
   1090         solve();
   1091     }
   1092     cout<<fixed<<setprecision(10);
   1093     cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
   1094 }
   1095 ```
   1096 
   1097 [1930I - Counting Is Fun](/contest/1930/problem/I "think-cell Round 1")
   1098 
   1099 Idea: [satyam343](/profile/satyam343 "Master satyam343")  
   1100 Full Solution: [Elegia](/profile/Elegia "Legendary Grandmaster Elegia")  
   1101 Editorial: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn")
   1102 
   1103 **Hint 1**
   1104 
   1105 [A167510](https://oeis.org/A167510)
   1106 
   1107 **Solution**
   1108 
   1109 It is convinient here to assign weights to $\mathtt{0} \to -1$ and $\mathtt{1} \to 1$.
   1110 
   1111 Given a string $t$, we can define the prefix sum $p$ of it's weights. For example, if $t=\mathtt{0010111}$, then $p=[0,-1,-2,-1,-2,-1,0,1]$. So that if $t$ is bad and $i$ is a index that violates the definition, then $\max(p_0,p_1,\ldots,p_{i-1}) \lt \min(p_i,p_{i+1},\ldots,p_n)$ if $s_i = \mathtt{0}$ or $\min(p_0,p_1,\ldots,p_{i-1}) \gt \max(p_i,p_{i+1},\ldots,p_n)$ if $s_i = \mathtt{1}$.
   1112 
   1113 Naturally, it is convinient to assume that $p_0 \lt p_n$. All string with $p_0 = p_n$ are clearly good and $p_0 \gt p_n$ is handled similarly. For strings with $p_0 \lt p_n$, the condition can only be violated on an index with $s_i = \mathtt{0}$.
   1114 
   1115 The solution works using PIE. Let us fix a set of positions $I$ that are bad, so that if $i \in I$, then $s_i =\mathtt{0}$ and $\max(p_0,p_1,\ldots,p_{i-1}) \lt \min(p_i,p_{i+1},\ldots,p_n)$. Then we need to count the number of ways to construct $p$ satisfying these conditions and then add it to the answer multiplied by $(-1)^{|I|}$.
   1116 
   1117 Suppose that $I = i_1,i_2,\ldots,i_k$. $t[1,i_1]$ and $t[i_k,n]$ need to be a ballot sequence of length $i_1-1$ and $n-i_k$ respectively (A001405, denote it as $f(n)$) while $t[i_j,i_{j+1}]$ needs to be bidirectional ballot sequence of length $i_{j+1}-i_j-1$ (A167510, denote it as $g(n)$). Note that in our definition of ballot sequence, we are do not require that prefixes and suffixes have strictly more $\mathtt{1}$ s thatn $\mathtt{0}$ s. It is the same sequence, but note that we need to shift it by a few places when refering to OEIS.
   1118 
   1119 The first $n$ terms of $f$ is easily computed in linear time. We will focus on how to compute the first $n$ terms of $g$ in $O(n \log^2 n)$.
   1120 
   1121 **Computing $g(n)$** Firstly, let us consider the number of bidirectional sequences with $\frac{n+k}{2}$ $\mathtt{1}$ s and $\frac{n-k}{2}$ $\mathtt{0}$ s. We will imagine this as lattice walks from $(0,0)$ to $(n,k)$ where $\mathtt{1} \to (1,1)$ and $\mathtt{0} \to (1,-1)$. If we touch the lines $y=-1$ or $y=k+1$, the walk is invalid.
   1122 
   1123 We can use the reflection method here, similar to a proof of Catalan. The number of valid walks is $#(*) - #(T) + #(TB) - #(TBT) ..... - #(B) + #(BT) - #(BTB) + .....$ where $#(BTB)$ denotes the number of walks that touch the bottom line, then the top line, then the bottom line, and then may continue to touch the top and bottom line after that.
   1124 
   1125 We have $#(*) =$ $\binom{n}{\frac{n+k}{2}}$, $#(T) =$ $ \binom{n}{\frac{n+k+2}{2}}$, $#(TB) =$ $ \binom{n}{\frac{n+3k+4}{2}}$, $#(TBT) =$ $ \binom{n}{\frac{n+3k+6}{2}}$, $\ldots$, $#(B) = $ $\binom{n}{\frac{n+k+2}{2}}$, $#(BT) =$ $ \binom{n}{\frac{n+k+4}{2}}$, $#(BTB) =$ $ \binom{n}{\frac{n+3k+6}{2}}$, $\ldots$
   1126 
   1127 This already gives us a method to compute $g(n)$ in $O(n \log n)$ since for a fixed $k$, we can compute the above sum in $O(\frac{n}{k})$, since only the first $O(\frac{n}{k})$ terms are not $0$.
   1128 
   1129 First, notice that we can aggregate them sums without iterating on $k$, for some fixed $j$, we can find the coefficient $c_j$ of $\binom{n}{\frac{n+j}{2}}$ across all $k$. Notice that this coefficient is independent across all $n$, so we only need to compute $c$ once.
   1130 
   1131 Now, note that $\binom{n}{\frac{n+z}{2}} = [x^z] (x^{-1} + x) ^ n$. So that $g(n) = [x^0] C \cdot (x^{-1} + x)^n$, where $C$ is the ogf of $c$.
   1132 
   1133 From this formulation, we can describe how to compute the first $n$ terms of $g$ in $O(n \log^2 n)$ using Divide and Conquer.
   1134 
   1135 $DnC(l,r,V)$ computes the $g(l) \ldots g(r)$ where $V$ is the coefficents between $[l-r,r-l]$ of $C \cdot (x^{-1} + x)^l$. $DnC(l,r,V)$ will call $DnC(l,m,V)$ and $DnC(m+1,r,V \cdot (x^{-1}+x)^{m-l+1})$. We have the reccurence $T(n) = 2 T(\frac{n}{2}) + O(n \log n)$ so $T(n) = O(n \log^2 n)$.
   1136 
   1137 Of course, for constant time speedup, you can choose to split the odd and even coefficients, but that is not needed.
   1138 
   1139 It is possible to compute the first $n$ of $g$ in $O(n \log n)$ but it does not improve the overall complexity of the solution.
   1140 
   1141 **Final Steps**
   1142 
   1143 Now that we obtained the $n$ terms of $f$ and $g$, let us return to the origial problem.
   1144 
   1145 If $s_i =\mathtt{0}$, define $dp_i = f(i-1) - \sum\limits_{s_j = \mathtt{0}} dp_j \cdot g(j-i-1)$. Then this contributes $f(n-i) \cdot dp_i$ to the number of bad strings.
   1146 
   1147 Again, we will use Divide and Conquer to perform this quickly.
   1148 
   1149 Briefly, $DnC(l,r)$ will compute the values of $dp[l,r]$ given that contributions from $dp[1,l-1]$ has been transferred to $dp[l,r]$ already.
   1150 
   1151 We will call $DnC(l,m)$, compute the contribution from $dp[l,m]$ to $dp[m+1,r]$ using FFT and then call $DnC(m+1,r)$. The complexity of this is $O(n \log^2 n)$.
   1152 
   1153 **Code(errorgorn)**
   1154 
   1155 ```
   1156 #include <bits/stdc++.h>
   1157 using namespace std;
   1158 
   1159 #define int long long
   1160 #define ll long long
   1161 #define ii pair<int,int>
   1162 #define iii tuple<int,int,int>
   1163 #define fi first
   1164 #define se second
   1165 #define endl '\n'
   1166 #define debug(x) cout << #x << ": " << x << endl
   1167 
   1168 #define pub push_back
   1169 #define pob pop_back
   1170 #define puf push_front
   1171 #define pof pop_front
   1172 #define lb lower_bound
   1173 #define ub upper_bound
   1174 
   1175 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
   1176 #define all(x) (x).begin(),(x).end()
   1177 #define sz(x) (int)(x).size()
   1178 
   1179 mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
   1180 
   1181 const int MOD=998244353;
   1182 
   1183 ll qexp(ll b,ll p,int m){
   1184     ll res=1;
   1185     while (p){
   1186         if (p&1) res=(res*b)%m;
   1187         b=(b*b)%m;
   1188         p>>=1;
   1189     }
   1190     return res;
   1191 }
   1192 
   1193 ll inv(ll i){
   1194 	return qexp(i,MOD-2,MOD);
   1195 }
   1196 
   1197 ll fix(ll i){
   1198 	i%=MOD;
   1199 	if (i<0) i+=MOD;
   1200 	return i;
   1201 }
   1202 
   1203 ll fac[1000005];
   1204 ll ifac[1000005];
   1205 
   1206 ll nCk(int i,int j){
   1207 	if (i<j) return 0;
   1208 	return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD;
   1209 }
   1210 
   1211 const ll mod = (119 << 23) + 1, root = 62; // = 998244353
   1212 // For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
   1213 // and 483 << 21 (same root). The last two are > 10^9.
   1214 typedef vector<ll> vl;
   1215 void ntt(vl &a) {
   1216 	int n = sz(a), L = 31 - __builtin_clz(n);
   1217 	static vl rt(2, 1);
   1218 	for (static int k = 2, s = 2; k < n; k *= 2, s++) {
   1219 		rt.resize(n);
   1220 		ll z[] = {1, qexp(root, mod >> s, mod)};
   1221 		rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
   1222 	}
   1223 	vector<int> rev(n);
   1224 	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
   1225 	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
   1226 	for (int k = 1; k < n; k *= 2)
   1227 		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
   1228 			ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
   1229 			a[i + j + k] = ai - z + (z > ai ? mod : 0);
   1230 			ai += (ai + z >= mod ? z - mod : z);
   1231 		}
   1232 }
   1233 vl conv(const vl &a, const vl &b) {
   1234 	if (a.empty() || b.empty()) return {};
   1235 	int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
   1236 	int inv = qexp(n, mod - 2, mod);
   1237 	vl L(a), R(b), out(n);
   1238 	L.resize(n), R.resize(n);
   1239 	ntt(L), ntt(R);
   1240 	rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
   1241 	ntt(out);
   1242 	return {out.begin(), out.begin() + s};
   1243 }
   1244 
   1245 int n;
   1246 string s;
   1247 
   1248 int c[100005];
   1249 int f[100005];
   1250 
   1251 void calc(int l,int r,vector<int> v){
   1252 	while (sz(v)>(r-l)*2+1) v.pob();
   1253 	
   1254 	if (l==r){
   1255 		f[l]=v[0];
   1256 		return;
   1257 	}
   1258 	
   1259 	int m=l+r>>1;
   1260 	
   1261 	calc(l,m,vector<int>(v.begin()+(r-m),v.end()));
   1262 	vector<int> a;
   1263 	int t=m-l+1;
   1264 	rep(x,0,t+1) a.pub(nCk(t,x)),a.pub(0);
   1265 	
   1266 	v=conv(v,a);
   1267 	calc(m+1,r,vector<int>(v.begin()+(2*t),v.end()));
   1268 }
   1269 
   1270 int ans[100005];
   1271 
   1272 void solve(int l,int r){
   1273 	if (l==r) return;
   1274 	int m=l+r>>1;
   1275 	solve(l,m);
   1276 	auto a=conv(vector<int>(ans+l,ans+m+1),vector<int>(f,f+(r-l)));
   1277 	rep(x,m+1,r+1) if (s[x]=='0') ans[x]=fix(ans[x]-a[x-1-l]);
   1278 	solve(m+1,r);
   1279 }
   1280 
   1281 signed main(){
   1282 	ios::sync_with_stdio(0);
   1283 	cin.tie(0);
   1284 	cout.tie(0);
   1285 	cin.exceptions(ios::badbit | ios::failbit);
   1286 	
   1287 	fac[0]=1;
   1288 	rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD;
   1289 	ifac[1000004]=inv(fac[1000004]);
   1290 	rep(x,1000005,1) ifac[x-1]=ifac[x]*x%MOD;
   1291 	
   1292 	rep(x,1,100005){
   1293 		c[x]++;
   1294 		
   1295 		int curr=x;
   1296 		while (curr<100005){
   1297 			if (curr+2<100005) c[curr+2]-=2;
   1298 			if (curr+4<100005) c[curr+4]++;
   1299 			if (curr+2*x+4<100005) c[curr+2*x+4]++;
   1300 			curr+=2*x+4;
   1301 		}
   1302 	}
   1303 	
   1304 	cin>>n;
   1305 	cin>>s;
   1306 	
   1307 	vector<int> v;
   1308 	rep(x,n+1,1) v.pub(fix(c[x]+(x>=2?c[x-2]:0LL)));
   1309 	calc(1,n,v);
   1310 	f[0]=1;
   1311 	
   1312 	int fin=qexp(2,n,MOD);
   1313 	rep(_,0,2){
   1314 		rep(x,0,n) ans[x]=(s[x]=='0')?nCk(x,x/2):0LL;
   1315 		solve(0,n-1);
   1316 		rep(x,0,n) if (s[x]=='0') fin=fix(fin-ans[x]*nCk((n-x-1),(n-x-1)/2));
   1317 		
   1318 		for (auto &it:s) it^=1;
   1319 	}
   1320 	
   1321 	cout<<fin<<endl;
   1322 }
   1323 ```