Número de pares de arreglos (A, B) tales que A es ascendente, B es descendente y A[i] ≤ B[i]

Dados dos números enteros N y M , la tarea es encontrar el número de pares de arreglos (A, B) tales que los arreglos A y B sean de tamaño M cada uno donde cada entrada de A y B es un número entero entre 1 y N tal que para cada i entre 1 y M , A[i] ≤ B[i] . También se da que la array A está ordenada en orden no descendente y B está ordenada en orden no ascendenteordenar. Dado que la respuesta puede ser muy grande, devuelva la respuesta módulo 10 ⁹ + 7 .

Ejemplos: 

Entrada: N = 2, M = 2 
Salida: 5 
1: A= [1, 1] B=[1, 1] 
2: A= [1, 1] B=[1, 2] 
3: A= [1 , 1] B=[2, 2] 
4: A= [1, 2] B=[2, 2] 
5: A= [2, 2] B=[2, 2]

Entrada: N = 5, M = 3 
Salida: 210 
 

Enfoque: observe que si hay un par válido de arrays A y B y si B se concatena después de A, la array resultante siempre será una array ascendente o no descendente de tamaño 2 * M. Cada elemento de (A + B) estará entre 1 y N (No es necesario que se tengan que utilizar todos los elementos entre 1 y N). Esto ahora simplemente convierte el problema dado para encontrar todas las combinaciones posibles de tamaño 2 * M donde cada elemento está entre 1 y N (con repeticiones permitidas) cuya fórmula es ^{2 * M + N – 1} C _{N – 1} o (2 * M + N – 1)! / ((2 * M)! * (N – 1)!).

A continuación se muestra la implementación del enfoque anterior:  

// C++ code of above approach
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
 
long long fact(long long n)
{
    if(n == 1)
        return 1;
    else
        return (fact(n - 1) * n) % mod;
}
 
// Function to return the count of pairs
long long countPairs(int m, int n)
{
    long long ans = fact(2 * m + n - 1) /
                    (fact(n - 1) * fact(2 * m));
    return (ans % mod);
}
 
// Driver code
int main()
{
    int n = 5, m = 3;
    cout << (countPairs(m, n));
    return 0;
}
 
// This code is contributed by mohit kumar 29

// Java code of above approach
class GFG
{
    final static long mod = 1000000007 ;
 
    static long fact(long n)
    {
        if(n == 1)
            return 1;
        else
            return (fact(n - 1) * n) % mod;
    }
     
    // Function to return the count of pairs
    static long countPairs(int m, int n)
    {
        long ans = fact(2 * m + n - 1) /
                   (fact(n - 1) * fact(2 * m));
         
        return (ans % mod);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 5, m = 3;
         
        System.out.println(countPairs(m, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
from math import factorial as fact
 
# Function to return the count of pairs
def countPairs(m, n):
    ans = fact(2 * m + n-1)//(fact(n-1)*fact(2 * m))
    return (ans %(10**9 + 7))
 
# Driver code
n, m = 5, 3
print(countPairs(m, n))

// C# code of above approach
using System;
 
class GFG
{
    static long mod = 1000000007 ;
 
    static long fact(long n)
    {
        if(n == 1)
            return 1;
        else
            return (fact(n - 1) * n) % mod;
    }
     
    // Function to return the count of pairs
    static long countPairs(int m, int n)
    {
        long ans = fact(2 * m + n - 1) /
                (fact(n - 1) * fact(2 * m));
         
        return (ans % mod);
    }
     
    // Driver code
    public static void Main()
    {
        int n = 5, m = 3;
         
        Console.WriteLine(countPairs(m, n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript code of above approach
var mod = 1000000007
 
function fact(n)
{
    if (n == 1)
        return 1;
    else
        return(fact(n - 1) * n) % mod;
}
 
// Function to return the count of pairs
function countPairs(m, n)
{
    var ans = fact(2 * m + n - 1) /
            (fact(n - 1) * fact(2 * m));
    return (ans % mod);
}
 
// Driver code
var n = 5, m = 3;
 
document.write(countPairs(m, n));
 
// This code is contributed by famously
 
</script>

210

Complejidad temporal: O(n + m)
Espacio auxiliar : O(max(n, m)).