Количество пар массивов (A, B), таких что A восходящий, B убывающий и A [i] ≤ B [i]

Опубликовано: 2 Декабря, 2021

Учитывая два целых числа N и M , задача состоит в том, чтобы найти количество пар массивов (A, B) таких, что массив A и B оба имеют размер M каждый, где каждая запись A и B представляет собой целое число от 1 до N, например что для каждого i от 1 до M A [i] ≤ B [i] . Также , учитывая , что массив А сортируются в порядке убывания не-и В сортируются в порядке возрастания без. Поскольку ответ может быть очень большим, верните ответ по модулю 10 ⁹ + 7 .

Примеры:

Input: N = 2, M = 2
Output: 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]
Input: N = 5, M = 3
Output: 210

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: обратите внимание, что если существует допустимая пара массивов A и B и если B объединяется после A, результирующий массив всегда будет либо восходящим, либо неубывающим массивом размером 2 * M. Каждый элемент (A + B) будет находиться в диапазоне от 1 до N (необязательно, чтобы использовались все элементы между 1 и N). Теперь это просто преобразует данную задачу в поиск всех возможных комбинаций размера 2 * M, где каждый элемент находится в диапазоне от 1 до N (с допустимыми повторениями), формула которого равна ^{2 * M + N - 1} C _{N - 1} или (2 * M + N - 1)! / ((2 * M)! * (N - 1)!).

Ниже представлена реализация описанного выше подхода:

CPP

 // 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

 # 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 #

 // 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

Выход:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы Структуры данных

Количество пар массивов (A, B), таких что A восходящий, B убывающий и A [i] ≤ B [i]

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

CPP

Ява

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ