HackerRank Combinatorics – Super Humble Matrix

Challenge: Super Humble Matrix

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464738687

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/super-humble-matrix/problem

Cerinta

Sherry likes matrices a lot, but her favorite ones are *humble matrices*. An $N \times M$ matrix (we'll call it $A$) is *humble* if:

- It contains all the elements in range $[1 , N \times M ]$ exactly once.
- For any $2$ elements $(i_1, j_1)$ and $(i_2, j_2)$ in matrix $A$:<br>
	If $i_1 + j_1 \lt i_2 + j_2$ , then $A_{i_1, j_1} \lt A_{i_2, j_2}$ should hold. 
    
Given $N$ and $M$, find and print the total number of possible humble matrices; as this number can be quite large, print your answer modulo $10^9+7$.

Input Format

Two space-separated integers, $N$ and $M$, respectively.

Output Format

Print the total number of humble matrices possible, modulo $10^9+7$.

**Sample Input 0**

    2 2
    
    
**Sample Output 0**

	2

**Sample Input 1**

    3 2
    
    
**Sample Output 1**

	4

Constraints

- $1 \le N,M \le 10^6$

**Scoring**

* $1 \le N,M \le 10^3$ for $30\%$ of the test data.  
* $1 \le N,M \le 10^6$ for $100\%$ of the test data.

Cod sursa

#include <iostream>
#include <vector>

using namespace std;


int main()
{
    int rows, columns; 
    cin >> rows >> columns;
    
    const int MOD = 1e9 + 7, MAX_SUM = rows + columns;
    vector <long long> factorial(MAX_SUM + 1); 
    factorial[0] = 1;
    for(int i = 1; i <= MAX_SUM; i++)
    {
        factorial[i] = (i*factorial[i - 1])%MOD;
    }
    
    long long no_of_ways = 1;
    for(int sum = 2; sum <= MAX_SUM; sum++)
    {
        int smallest_row = max(sum - columns, 1), largest_row = min(sum - 1, rows);
        int diagonal_size = largest_row - smallest_row + 1;
        long long no_of_ways_to_permute_diagonal = factorial[diagonal_size];
        
        no_of_ways *= no_of_ways_to_permute_diagonal;
        no_of_ways %= MOD;
    }

    cout << no_of_ways << "\n";
    return 0;
}