Soluție HackerRank pentru Merge List, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Merge List
- Domeniu: Combinatorics
- Limbaj: C++14
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
Cerință
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≤ T ≤ 10
+ 1≤ N ≤ 100
+ 1≤ M ≤ 100
Cod sursă
#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;
}
}