codeforces-scrape

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

1747.md (19304B)


      1 Source: https://codeforces.com/blog/entry/108782
      2 
      3 I hope you all liked the round. Please share your feedback in the comments section.
      4 
      5 # [1747A — Two Groups](https://codeforces.com/contest/1747/problem/A)
      6 
      7 **Hint**
      8 
      9 How about putting all positive numbers in one group and negative in second group
     10 
     11 **Tutorial**
     12 
     13 Let $S$ denotes sum of element of array $a$.
     14 
     15 **Claim**: Answer is $|S|$.
     16 
     17 **Proof**: Let sum of all positive elements is $S_{pos}$ and sum of all negative elements $S_{neg}$. Put all positive numbers in first group and negative numbers in second group. We get $||S_{pos}| - |S_{neg}|| = |S|$.
     18 
     19 Let's prove that we can not do better than that. Let $S_1$ denotes sum of elements of first group and $S_2$ denotes sum of elements of second group. We have $|S_1| - |S_2| \leq |S_1 + S_2| = |S|$. Hence $|S|$ is the upperbound for the answer.
     20 
     21 **Solution**
     22 
     23 ```
     24 // Jai Shree Ram
     25 #include<bits/stdc++.h>
     26 using namespace std;
     27 
     28 #define rep(i,a,n)     for(int i=a;i<n;i++)
     29 #define ll             long long
     30 #define int            long long
     31 #define pb             push_back
     32 #define all(v)         v.begin(),v.end()
     33 #define endl           "\n"
     34 #define x              first
     35 #define y              second
     36 #define gcd(a,b)       __gcd(a,b)
     37 #define mem1(a)        memset(a,-1,sizeof(a))
     38 #define mem0(a)        memset(a,0,sizeof(a))
     39 #define sz(a)          (int)a.size()
     40 #define pii            pair<int,int>
     41 #define hell           1000000007
     42 #define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
     43 
     44 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
     45 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
     46 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
     47 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
     48 
     49 int solve(){
     50  		int n; cin >> n;
     51  		int s = 0;
     52  		for(int i = 0; i < n; i++){
     53  			int x; cin >> x;
     54  			s += x;
     55  		}
     56  		cout << abs(s) << endl;
     57  return 0;	
     58 }
     59 signed main(){
     60     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
     61     //freopen("input.txt", "r", stdin);
     62     //freopen("output.txt", "w", stdout);
     63     #ifdef SIEVE
     64     sieve();
     65     #endif
     66     #ifdef NCR
     67     init();
     68     #endif
     69     int t=1;cin>>t;
     70     while(t--){
     71         solve();
     72     }
     73     return 0;
     74 }
     75 ```
     76 
     77 # [1747B — BAN BAN](https://codeforces.com/contest/1747/problem/B)
     78 
     79 **Hint 1**
     80 
     81 Instead of subsequences solve for substrings. That is there should not be any substring $\texttt{BAN}$ after performing operations.
     82 
     83 **Hint 2**
     84 
     85 In one operation you can destroy atmost $2$ substrings. Find minimum operations to destroy $n$ substrings.
     86 
     87 **Answer**
     88 
     89 $\left \lceil\frac{n}{2}\right \rceil $
     90 
     91 **Hint 3**
     92 
     93 Congrats, you have solved for subsequences also!
     94 
     95 **Tutorial**
     96 
     97 No subsequences of string $\texttt{BAN}$ would also mean no substrings of $\texttt{BAN}$ in original string. Let minimum number of operations to have no substrings of $\texttt{BAN}$ be $x$, it would be also be the lower bound for having no subsequences of string $\texttt{BAN}$.
     98 
     99 **Claim**: $x = \left \lceil\frac{n}{2}\right \rceil$.
    100 
    101 **Proof**: Swap $i$-th $\texttt{B}$ from start with $i$-th $\texttt{N}$ from end for $1 \leq i \leq \left \lceil\frac{n}{2}\right \rceil$. We can see that, no substrings of $\texttt{BAN}$ exists after performing $ \left \lceil\frac{n}{2}\right \rceil$ operations. Since we can only destroy atmost $2$ substrings in one operations, $\left \lceil\frac{n}{2}\right \rceil$ is minimum possible.
    102 
    103 Now if you see clearly, after performing above operations, there does not exist any subsequence of string $\texttt{BAN}$ in original string. Hence $\left \lceil\frac{n}{2}\right \rceil$ is also the answer for the original problem.
    104 
    105 **Solution**
    106 
    107 ```
    108 // Jai Shree Ram  
    109   
    110 #include<bits/stdc++.h>
    111 using namespace std;
    112 
    113 #define rep(i,a,n)     for(int i=a;i<n;i++)
    114 #define ll             long long
    115 #define int            long long
    116 #define pb             push_back
    117 #define all(v)         v.begin(),v.end()
    118 #define endl           "\n"
    119 #define x              first
    120 #define y              second
    121 #define gcd(a,b)       __gcd(a,b)
    122 #define mem1(a)        memset(a,-1,sizeof(a))
    123 #define mem0(a)        memset(a,0,sizeof(a))
    124 #define sz(a)          (int)a.size()
    125 #define pii            pair<int,int>
    126 #define hell           1000000007
    127 #define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
    128 
    129 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
    130 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
    131 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
    132 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
    133 
    134 int solve(){
    135  		int n; cin >> n;
    136  		cout << n/2 + n % 2 << endl;
    137  		int l = 1, r = 3*n;
    138  		while(l < r){
    139  			cout << l << " " << r << endl;
    140  			l += 3;
    141  			r -= 3;
    142  		}
    143  return 0;
    144 }
    145 signed main(){
    146     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    147     //freopen("input.txt", "r", stdin);
    148     //freopen("output.txt", "w", stdout);
    149     #ifdef SIEVE
    150     sieve();
    151     #endif
    152     #ifdef NCR
    153     init();
    154     #endif
    155     int t=1;cin>>t;
    156     while(t--){
    157         solve();
    158     }
    159     return 0;
    160 }
    161 ```
    162 
    163 # [1747C — Swap Game](https://codeforces.com/contest/1747/problem/c)
    164 
    165 **Hint 1**
    166 
    167 Divide problem into two different cases. When $a_1 \gt \min(a)$ and when $a_1 = \min(a)$.
    168 
    169 **Hint 2**
    170 
    171 You do not need more hints to solve the problem.
    172 
    173 **Tutorial**
    174 
    175 **Case 1**: $a_1 \gt \min(a)$
    176 
    177 $\texttt{Alice}$ can force the $\texttt{Bob}$ to always decrease the minimum element by always choosing minimum element of $a$ in her turn. Where as $\texttt{Bob}$ can not do much, all other elements he would swap with would be greater than or equal to $\min(a)$. Even if there exists multiple minimums in $a$, In first move $\texttt{Alice}$ would decrease from $a_1$, hence in this case $\texttt{Alice}$ would always win.
    178 
    179 **Case 2**: $a_1 = \min(a)$
    180 
    181 In this case optimal startegy for $\texttt{Bob}$ would be to always chhose minimum element of the array, which is $a_1$. $\texttt{Alice}$ would always be swapping the element greater than $a_1$ in her turn, hence in the case $\texttt{Bob}$ would always win
    182 
    183 **Solution**
    184 
    185 ```
    186 // Jai Shree Ram  
    187   
    188 #include<bits/stdc++.h>
    189 using namespace std;
    190 
    191 #define rep(i,a,n)     for(int i=a;i<n;i++)
    192 #define ll             long long
    193 #define int            long long
    194 #define pb             push_back
    195 #define all(v)         v.begin(),v.end()
    196 #define endl           "\n"
    197 #define x              first
    198 #define y              second
    199 #define gcd(a,b)       __gcd(a,b)
    200 #define mem1(a)        memset(a,-1,sizeof(a))
    201 #define mem0(a)        memset(a,0,sizeof(a))
    202 #define sz(a)          (int)a.size()
    203 #define pii            pair<int,int>
    204 #define hell           1000000007
    205 #define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
    206 
    207 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
    208 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
    209 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
    210 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
    211 
    212 int solve(){
    213  		int n; cin >> n;
    214  		vector<int> a(n);
    215  		for(auto &i:a)cin >> i;
    216  		sort(a.begin() + 1,a.end());
    217  		cout << (a[0] > a[1] ? "Alice" : "Bob") << endl;
    218  return 0;
    219 }
    220 signed main(){
    221     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    222     //freopen("input.txt", "r", stdin);
    223     //freopen("output.txt", "w", stdout);
    224     #ifdef SIEVE
    225     sieve();
    226     #endif
    227     #ifdef NCR
    228     init();
    229     #endif
    230     int t=1;cin>>t;
    231     while(t--){
    232         solve();
    233     }
    234     return 0;
    235 }
    236 ```
    237 
    238 # [1747D — Yet another Problem](https://codeforces.com/contest/1747/problem/D)
    239 
    240 **Hint 1**
    241 
    242 Forget queries, they are just here to make problem look complicated. Solve for $q = 1$.
    243 
    244 **Hint 2**
    245 
    246 XOR of array does not change after operations. Hence if initially XOR is not equal to $0$, answer is $-1$. Is this condition sufficient?
    247 
    248 **Answer**
    249 
    250 No, We need one more condition
    251 
    252 **Hint 3**
    253 
    254 There must exist some prefix of odd size, such that xor of elements of that prefix is $0$.
    255 
    256 **Tutorial**
    257 
    258 First forget queries, solve for single array $a$.
    259 
    260 Let's make some observations.
    261 
    262 1. Xor of array does not change after each operation
    263 2. Look at the set of prefix XORs while doing operations. Its size always decreases or remains same after each operation. Infact we can further reduce it to parities. Let $S_{0}$, $S_{1}$ be sets of prefix XOR's of parities $0$ and $1$ respectively. After each operation new sets $S'_{0}$, $S'_{1}$ will be subsets of $S_{0}$ and $S_1$ respectively.
    264 
    265 So necessary conditions for answer to exist is that xor of array should be $0$ and $S_{1}$ should contains $0$.
    266 
    267 Now comes to minimum operations.
    268 
    269 **Claim:** If above conditions are satisfied, its always possible to make all elements $0$ in less than or equal to $2$ operations
    270 
    271 **Proof:** Let length of array be $n$.
    272 
    273 **Case 1:** $n$ is odd
    274 
    275 Just apply the operation on whole array.
    276 
    277 **Case 2:** $n$ is even
    278 
    279 There will exists some odd size prefix $j$ such that xor of its elements is $0$. Apply operation on $[1,j]$ and $[j + 1,n]$. It can happen that $j = 1$ or $j = n - 1$, in that case we only need one operation, because other remaining element would already be equal to $0$.
    280 
    281 To solve for queries, you just need to check for odd prefix, which can be done using some data structure like $\texttt{std::map}$ or $\texttt{std::set}$ in C++. Do not forget to check the case when all elements are already $0$.
    282 
    283 **Solution**
    284 
    285 ```
    286 #include<bits/stdc++.h>
    287 using namespace std ;
    288 
    289 #define ll              long long 
    290 #define pb              push_back
    291 #define all(v)          v.begin(),v.end()
    292 #define sz(a)           (ll)a.size()
    293 #define F               first
    294 #define S               second
    295 #define INF             2000000000000000000
    296 #define popcount(x)     __builtin_popcountll(x)
    297 #define pll             pair<ll,ll>
    298 #define pii             pair<int,int>
    299 #define ld              long double
    300 
    301 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
    302 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
    303 
    304 #ifdef LOCAL
    305 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
    306 #else
    307 #define debug(...) 3000
    308 #endif
    309 
    310 int _runtimeTerror_()
    311 {
    312     int n, Q;
    313     cin >> n >> Q;
    314     map<int, int> odd, even;
    315     vector<int> last_nz(n + 1, 0), last(n + 1, -1), pxor(n + 1, 0);
    316     vector<int> a(n + 1);
    317     even[0] = 0;
    318     int cur = 0;
    319     for(int i=1;i<=n;++i) {
    320     	cin >> a[i];
    321     	cur ^= a[i];
    322     	pxor[i] = cur;
    323     	if(a[i] == 0) {
    324     		last_nz[i] = last_nz[i - 1];
    325     	}
    326     	else {
    327     		last_nz[i] = i;
    328     	}
    329     	if(i & 1) {
    330     		if(even.count(cur)) {
    331     			last[i] = even[cur];
    332     		}
    333     		odd[cur] = i;
    334     	}
    335     	else {
    336     		if(odd.count(cur)) {
    337     			last[i] = odd[cur];
    338     		}
    339     		even[cur] = i;
    340     	}
    341     }
    342     while(Q--) {
    343     	int l, r;
    344     	cin >> l >> r;
    345     	if(pxor[l - 1] != pxor[r]) {
    346     		cout << "-1\n";
    347     	}
    348     	else if(last_nz[r] < l) {
    349     		cout << "0\n";
    350     	}
    351     	else if(r % 2 == l % 2) {
    352     		cout << "1\n";
    353     	}
    354     	else if(a[l] == 0 or a[r] == 0) {
    355     		cout << "1\n";
    356     	}
    357     	else if(last[r] >= l) {
    358     		cout << "2\n";
    359     	}
    360     	else {
    361     		cout << "-1\n";
    362     	}
    363     }
    364     return 0;
    365 }
    366 
    367 int main()
    368 {
    369     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    370     #ifdef runSieve
    371         sieve();
    372     #endif
    373     #ifdef NCR
    374         initncr();
    375     #endif
    376     int TESTS = 1;
    377     //cin >> TESTS;
    378     while(TESTS--) {
    379         _runtimeTerror_();
    380     }
    381     return 0;
    382 }	 	
    383 ```
    384 
    385 # [1747E — List Generation](https://codeforces.com/contest/1747/problem/E)
    386 
    387 **Hint 1**
    388 
    389 Change your point of view from array to grid. Think of pair of arrays as paths in grid of size $(n + 1) \times (m + 1)$.
    390 
    391 **Hint 2**
    392 
    393 First try counting number of good pair of arrays.
    394 
    395 **answer**
    396 
    397 Number of good pairs of arrays comes out to be $\sum\limits_{k = 0}{k = \min(n,m} \binom{n}{k} \cdot \binom{m}{k} \cdot 2^{n + m - k - 1}$
    398 
    399 **Tutorial**
    400 
    401 Given problem is equivalent to:
    402 
    403 You are currently at cell $(0,0)$. From any cell $(x,y)$ you can jump to cell $(x',y')$ such that $x \leq x' \leq n$ , $y \leq y' \leq m$ and $(x,y) \neq (x',y')$. Find sum of number of visited cells over all paths starting from $(0,0)$ and ending at $(n,m)$. Denote the required value by $f(n,m)$.
    404 
    405 Directly thinking in $2$ dimensions is difficult, lets first solve for case when $n = 0$ or $m = 0$. WLOG, assuming $m = 0$. We can solve this case using some binomials.
    406 
    407 $f(n,0) = 2^{n - 1} \cdot \frac{n + 3}{2}$, $n \gt 0$.
    408 
    409 Now, we can divide all possible paths from $(0,0)$ to $(n,m)$ into several classes of one dimensional paths.
    410 
    411 These classes are defined by what I call *breakpoints*. When we passes the breakpoint we turns right. Hence we can group paths by fixing the number of breakpoints.
    412 
    413 WLOG, Assuming $n \geq m$. For $k$ breakpoints there are $\binom{n}{k} \cdot \binom{m}{k}$ ways to select for $0 \leq k \leq m $. For a path with $k$ breakpoints, $n + m - k$ points are *optional*, that is there will exist $2^{n + m - k}$ paths with $k$ breakpoints. It is not difficult to see that sum of number of visited cells over paths with $k$ breakpoints turned out to be $f(n + m - k,0) + 2^{n + m - k - 1}\cdot k$. Hence we can write $f(n,m) = \sum\limits_{k = 0}^{m} \binom{n}{k} \cdot \binom{m}{k} \cdot (f(n + m - k,0) + 2^{n + m - k - 1}\cdot k)$
    414 
    415 Time complexity of the solution would be $\mathcal{O}(\min(n,m))$
    416 
    417 **Solution**
    418 
    419 ```
    420 // Jai Shree Ram  
    421   
    422 #include<bits/stdc++.h>
    423 using namespace std;
    424 
    425 #define rep(i,a,n)     for(int i=a;i<n;i++)
    426 #define ll             long long
    427 #define int            long long
    428 #define pb             push_back
    429 #define all(v)         v.begin(),v.end()
    430 #define endl           "\n"
    431 #define x              first
    432 #define y              second
    433 #define gcd(a,b)       __gcd(a,b)
    434 #define mem1(a)        memset(a,-1,sizeof(a))
    435 #define mem0(a)        memset(a,0,sizeof(a))
    436 #define sz(a)          (int)a.size()
    437 #define pii            pair<int,int>
    438 #define hell           1000000007
    439 #define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
    440 
    441 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
    442 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
    443 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
    444 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
    445 
    446 const int MOD = hell;
    447  
    448 struct mod_int {
    449     int val;
    450  
    451     mod_int(long long v = 0) {
    452         if (v < 0)
    453             v = v % MOD + MOD;
    454  
    455         if (v >= MOD)
    456             v %= MOD;
    457  
    458         val = v;
    459     }
    460  
    461     static int mod_inv(int a, int m = MOD) {
    462         int g = m, r = a, x = 0, y = 1;
    463  
    464         while (r != 0) {
    465             int q = g / r;
    466             g %= r; swap(g, r);
    467             x -= q * y; swap(x, y);
    468         }
    469  
    470         return x < 0 ? x + m : x;
    471     }
    472  
    473     explicit operator int() const {
    474         return val;
    475     }
    476  
    477     mod_int& operator+=(const mod_int &other) {
    478         val += other.val;
    479         if (val >= MOD) val -= MOD;
    480         return *this;
    481     }
    482  
    483     mod_int& operator-=(const mod_int &other) {
    484         val -= other.val;
    485         if (val < 0) val += MOD;
    486         return *this;
    487     }
    488  
    489     static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    490            #if !defined(_WIN32) || defined(_WIN64)
    491                 return x % m;
    492            #endif
    493            unsigned x_high = x >> 32, x_low = (unsigned) x;
    494            unsigned quot, rem;
    495            asm("divl %4\n"
    496             : "=a" (quot), "=d" (rem)
    497             : "d" (x_high), "a" (x_low), "r" (m));
    498            return rem;
    499     }
    500  
    501     mod_int& operator*=(const mod_int &other) {
    502         val = fast_mod((uint64_t) val * other.val);
    503         return *this;
    504     }
    505  
    506     mod_int& operator/=(const mod_int &other) {
    507         return *this *= other.inv();
    508     }
    509  
    510     friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
    511     friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
    512     friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
    513     friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
    514  
    515     mod_int& operator++() {
    516         val = val == MOD - 1 ? 0 : val + 1;
    517         return *this;
    518     }
    519  
    520     mod_int& operator--() {
    521         val = val == 0 ? MOD - 1 : val - 1;
    522         return *this;
    523     }
    524  
    525     mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
    526     mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }
    527  
    528     mod_int operator-() const {
    529         return val == 0 ? 0 : MOD - val;
    530     }
    531  
    532     bool operator==(const mod_int &other) const { return val == other.val; }
    533     bool operator!=(const mod_int &other) const { return val != other.val; }
    534  
    535     mod_int inv() const {
    536         return mod_inv(val);
    537     }
    538  
    539     mod_int pow(long long p) const {
    540         assert(p >= 0);
    541         mod_int a = *this, result = 1;
    542  
    543         while (p > 0) {
    544             if (p & 1)
    545                 result *= a;
    546  
    547             a *= a;
    548             p >>= 1;
    549         }
    550  
    551         return result;
    552     }
    553  
    554     friend ostream& operator<<(ostream &stream, const mod_int &m) {
    555         return stream << m.val;
    556     }
    557     friend istream& operator >> (istream &stream, mod_int &m) {
    558         return stream>>m.val;   
    559     }
    560 };
    561 #define NCR
    562 const int N = 5e6 + 5;
    563 mod_int fact[N],inv[N],invv[N];
    564 void init(int n=N){
    565 	fact[0]=inv[0]=inv[1]=1;
    566         invv[0] = invv[1] = 1;
    567 	rep(i,1,N)fact[i]=i*fact[i-1];
    568 	rep(i,2,N){
    569         invv[i] = (MOD - MOD/i)*invv[MOD % i];
    570         inv[i] = invv[i]*inv[i - 1];
    571     }
    572 }
    573 mod_int C(int n,int r){
    574 	if(r>n || r<0)return 0;
    575 	return fact[n]*inv[n-r]*inv[r];
    576 }
    577 
    578 int solve(){
    579  		int n,m; cin >> n >> m;
    580  		if(m > n)swap(n,m);
    581  		auto brute = [&](){
    582  			vector<vector<mod_int>>dp(n + 1,vector<mod_int>(m + 1));
    583  			vector<vector<mod_int>>exp(n + 1,vector<mod_int>(m + 1));
    584  			dp[0][0] = 1;
    585  			exp[0][0] = 0;
    586  			for(int i = 0; i <= n; i++){
    587  				for(int j = 0; j <= m; j++){
    588  					if(i + j == 0)continue;
    589  					for(int x = 0; x <= i; x++){
    590  						for(int y = 0; y <= j; y++){
    591  							if(x + y == i + j)continue;
    592  							dp[i][j] += dp[x][y];
    593  							exp[i][j] += (exp[x][y] + dp[x][y]);
    594  						}
    595  					}
    596  				}
    597  			}
    598  			return exp[n][m] + dp[n][m];
    599  		};
    600  		auto correct = [&](){
    601                         mod_int in = mod_int(2).inv();
    602  			auto d = [&](int x){
    603  				mod_int val = x + 1;
    604  				return val * in;
    605  			};
    606  			mod_int ans = 0;
    607                         mod_int pw = mod_int(2).pow(n + m);
    608  			for(int i = 0; i <= m; i++){
    609                                 pw *= in;
    610  				ans += C(n,i)*C(m,i)*pw*(i + d(n + m - i) + 1);
    611  			}
    612  			return ans;
    613  		};
    614  		cout << correct() << endl;
    615 
    616  return 0;
    617 }
    618 signed main(){
    619     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    620     //freopen("input.txt", "r", stdin);
    621     //freopen("output.txt", "w", stdout);
    622     #ifdef SIEVE
    623     sieve();
    624     #endif
    625     #ifdef NCR
    626     init();
    627     #endif
    628     int t=1;cin>>t;
    629     while(t--){
    630         solve();
    631     }
    632     return 0;
    633 }
    634 ```