HackerRank Fundamentals – Sherlock and Permutations

Challenge: Sherlock and Permutations

Subdomeniu: Fundamentals (fundamentals)

Scor cont: 20.0 / 20

Submission status: Accepted

Submission score: 1.0

Submission ID: 464722668

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/sherlock-and-permutations/problem

Cerinta

Watson asks Sherlock:  
Given a string _S_ of _N_ `0's` and _M_ `1's`, how many unique permutations of this string start with `1`?   

Help Sherlock by printing the answer modulo (_10<sup>9</sup>+7_).   

**Input Format**   
First line contains _T_, the number of test cases.  
Each test case consists of _N_ and _M_ separated by a space.

**Output Format**   
For each test case, print the answer modulo (_10<sup>9</sup>+7_).

**Constraints**  
1 ≤ T ≤ 200  
1 ≤ N,M ≤ 1000  

**Sample Input**   

	2
	1 1
	2 3
    
**Sample Output**      
	
    1
    6

**Explanation**  
Test1: Out of all unique permutations ie. `01` and `10`, only second permutation satisfies. Hence, output is 1.  
Test2: Out of all unique permutations ie. `00111 01011 01101 01110 10011 10101 10110 11001 11010 11100`, only `10011 10101 10110 11001 11010 11100` satisfy. Hence, output is 6.

Cod sursa

#include <bits/stdc++.h>
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define div 1000000007

using namespace std;

int com[2017][2017];

int main()
{
    int n,r,a,b,c;
    for(n=0; n<=2000; n++)
    {
        for(r=0; r<=n; r++)
        {
            if(r==0 || r==n)
                com[n][r]=1;
            else
                com[n][r]=(com[n-1][r-1]+com[n-1][r])%1000000007;
        }
    }
    cin>>c;
    while(c--)
    {
        cin>>a>>b;
        cout<<com[a+b-1][b-1]<<endl;
    }

    return 0;
}