HackerRank Combinatorics – Merge List

Challenge: Merge List

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464729864

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/merge-list/problem

Cerinta

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 $[1, 2, 3]$ and $[4,5,6]$, $[1,4,2,3,5,6]$ is a valid merge, while $[1,4,3,2,5,6]$ is not a valid merge because $3$ appears before $2$. 

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

Input Format

The first line contains an integer $T$, the number of test cases.  
Each of the next $T$ lines contains two integers $N$ and $M$.

Output Format

Print the value of the answer $\bmod 10^9+7$.

Constraints

+ $ 1\le T \le 10$  
+ $ 1\le N \le  100$  
+ $ 1\le M \le  100$

Cod sursa

#include<bits/stdc++.h>

using namespace std;

const long mod=1000000007;

long factorial[201]={1};

void precalculate()
{
    long fact=1;
    for(int i=1;i<=200;i++)
    {
        fact=(fact*i)%mod;
        factorial[i]=fact;
    }
}

long egcd(long a,long b,long *x,long *y)
{
    if(a==0)
    {
        *x=0;
        *y=1;
        return b;
    }
    long x1,y1;
    long gcd=egcd(b%a,a,&x1,&y1);
    *x=y1-(b/a)*x1;
    *y=x1;
    return gcd;
}

long  modInverse(long a,long m)
{
    long x,y;
    long g=egcd(a,mod,&x,&y);
    long ans=(x%mod+mod)%mod;
    return ans;
}

int main()

{
   precalculate();
   int T;
   cin>>T;
   int n,m;
   while(T--)
   {
       cin>>n>>m;
       long upore=(factorial[n+m])%mod;
       long niche =((factorial[n]*factorial[m])%mod);
       long ans=modInverse(niche,mod);
       long res=(ans*upore)%mod;
       cout<<res<<endl;
   }
}