Hackerrank - Merge List

Shashank is very excited after learning about the linked list. He learned about how to merge two linked lists. When we merge two linked lists, the order of the elements of each list doesn't change. For example, if we merge and ,  is a valid merge, while  is not a valid merge because  is appears before.

Shashank wants you to solve a problem for him: You are given two lists having sizes  and . How many ways can we merge both the lists? It is given that all  elements are distinct. As your answer can be quite large, Shashank wants you to print it .

Input Format 
The first line contains an integer , the number of test cases. 
Each of the next  lines contains two integers  and .

Output Format 
Print the value of the answer .

Constraints

 
 

Sample Input

1
2 2

Sample Output

6

Explanation

Suppose the two lists are  and . The different ways of merging these lists are given below:

 
 
 
 
 

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos (0.0);
8.  
9. int _Int(){int x; scanf("%d", &x); return x;}
10. LL _LLi(){LL x; scanf("%lld", &x); return x;}
11. void pruts(){puts("-1");exit(EXIT_SUCCESS);}
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. string s, Ans[ (1<<16)+2 ];
31.  
32. void Love(){
33.     int t = _Int();
34.     while( t-- ){
35.         int n = _Int();
36.         cin >> s;
37.         int k = 0;
38.         for( int i = 1; i < ( 1 << n ); i++ ){
39.             int ind = 0;
40.             int v = i;
41.             string temp;
42.             while( v ){
43.                 if( v&1 )temp.pb(s[ind]);
44.                 ind++;
45.                 v >>= 1;
46.             }
47.             if( temp.size() )Ans[k++] = temp;
48.             temp.clear();
49.         }
50.         sort(Ans, Ans+k);
51.         for( int i = 0; i < k; i++ )cout << Ans[i] << endl;
52.         for( int i = 0; i < k; i++ )Ans[i].clear();
53.     }
54. }
55.  
56. int main(){
57.     #ifndef ONLINE_JUDGE
58. //        freopen("in.txt", "r", stdin);
59. //        freopen("n.txt", "w", stdout);
60.     #endif
61.     Love();
62.     return 0;
63. }