LT14-Editorial

editorial
, ,
1

Problem Link

Loop Through

Author:isag2008

Difficulty

MEDIUM

Prerequisites

Math

Problem Statement

Harrison owns a coin museum. He wants to place all the coins in a matrix representation (size R x C) so that all the coins are visible from the top and side view.
He has exactly one coin of all denominations from 1 to (R x C).
For all the coins to be visible, the coin matrix must satisfy the following rule:

For any 2 elements (i1, j1) and (i2, j2) in the matrix X

If i1 + j1 < i2 + j2 then
Xi1, j1 < Xi2, j2 should hold.


Given R and C, find and print the total number of possible ways of placing the coins; return your answer
in modulo 109+7.

Approach

As written in the Problem Statement, we want to find the total number of matrices where:
If i1 + j1 < i2 + j2, then Xi1,j1 < Xi2,j2

Note that the value of i+j remains same for any specific diagonal of the matrix. Therefore, all the values in the particular diagonal must be greater than all the values in the diagonal above it. The Problem also mentions that each value in the matrix must be unique and lie in the range [1, RxC]. Therefore, the answer for our problem is (d1)! x (d2)! x (d3)! x (dR+C-1)! where di is total number of elements in ith diagonal.

Solution

 #include<bits/stdc++.h>
 using namespace std;
 #define pb push_back
 #define pi pair<ll,ll>
 #define f first
 #define s second
 #define ll long long
 #define rep(i,n) for(int i=0;i<n;i++)
 #define mod 1000000007
 ll fact[2000011];
 int main(){
     int N,M;
     cin >> N >> M;
     fact[0]=1;
      for(ll i=1;i<=N+M;i++){
         fact[i]=i*fact[i-1];
         fact[i]%=mod;
     }
     ll ans=1;
     int i=N;
     int j=1;
     for(int d=N-1;d>=1-M;d--){
        int cnt=j-(i-d)+1;
        ans*=fact[cnt];
        ans%=mod;
        i--;
        j++;
        i=max(i,1);
        j=min(j,M);
     }
    cout<<ans;
 }