Soluție HackerRank pentru Super Humble Matrix, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Super Humble Matrix
- Domeniu: Combinatorics
- Limbaj: C++14
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
Cerință
Sherry likes matrices a lot, but her favorite ones are *humble matrices*. An N × M matrix (we'll call it A) is *humble* if:
- It contains all the elements in range [1 , N × M ] exactly once.
- For any 2 elements (i_1, j_1) and (i_2, j_2) in matrix A:
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 ≤ N,M ≤ 10^6
Scoring
* 1 ≤ N,M ≤ 10^3 for 30% of the test data.
* 1 ≤ N,M ≤ 10^6 for 100% of the test data.
Cod sursă
#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;
}