Рубрики

Количество массивов, в которых все смежные элементы таковы, что один из них делит другой

Даны два положительных целых числа n и n . Задача состоит в том, чтобы найти количество массивов размера n, которые можно сформировать так, чтобы:

  1. Каждый элемент находится в диапазоне [1, м]
  2. Все смежные элементы таковы, что один из них делит другой, т. Е. Элемент A i делит A i + 1, или A i + 1 делит A i + 2 .

Примеры:

Input : n = 3, m = 3.
Output : 17
{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1}, 
{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},
{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},
{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1}, 
{3,3,3} are possible arrays.

Input : n = 1, m = 10.
Output : 10

Мы пытаемся найти количество возможных значений в каждом индексе массива. Во-первых, при индексе 0 все значения возможны от 1 до m. Теперь наблюдаем за каждым индексом, мы можем достичь либо его кратного или его множителя. Итак, предварительно вычислите это и сохраните для всех элементов. Следовательно, для каждой позиции i, заканчивающейся целым числом x, мы можем перейти к следующей позиции i + 1, где массив заканчивается целым числом, кратным x или множителем x. Кроме того, кратное х или фактор х должен быть меньше, чем м.
Итак, мы определяем двумерный массив dp [i] [j], который является номером возможного массива (делимого смежного элемента) размера i с j в качестве первого элемента индекса.

1 <= i <= m, dp[1][m] = 1.
for 1 <= j <= m and 2 <= i <= n
  dp[i][j] = dp[i-1][j] + number of factor 
             of previous element less than m 
             + number of multiples of previous
             element less than m.

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

C ++

// C ++ программа для подсчета количества массивов
// такого размера n, что каждый элемент
// в диапазоне [1, m] и прилегающие
// делится
#include <bits/stdc++.h>
#define  MAX 1000

using namespace std;

  

int numofArray(int n, int m)

{

    int dp[MAX][MAX];

  

    // Для хранения факторов.

    vector<int> di[MAX];

  

    // Для хранения кратных.

    vector<int> mu[MAX];

  

    memset(dp, 0, sizeof dp);

    memset(di, 0, sizeof di);

    memset(mu, 0, sizeof mu);

  

    // вычисление коэффициентов и коэффициентов

    // элементов [1 ... m].

    for (int i = 1; i <= m; i++)

    {

        for (int j = 2*i; j <= m; j += i)

        {

            di[j].push_back(i);

            mu[i].push_back(j);

        }

        di[i].push_back(i);

    }

  

    // Инициализация массива размера 1 для

    // каждый я <= м.

    for (int i = 1; i <= m; i++)

        dp[1][i] = 1;

  

    // Расчет количества возможных массивов

    // размера i и начинающегося с j.

    for (int i = 2; i <= n; i++)

    {

        for (int j = 1; j <= m; j++)

        {

            dp[i][j] = 0;

  

            // Для всех предыдущих возможных значений.

            // Добавление количества факторов.

            for (auto x:di[j])

                dp[i][j] += dp[i-1][x];

  

            // Добавляем номер кратно.

            for (auto x:mu[j])

                dp[i][j] += dp[i-1][x];

        }

    }

  

    // Подсчет общего количества массива

    // которые начинаются с [1 ... m].

    int ans = 0;

    for (int i = 1; i <= m; i++)

    {

        ans += dp[n][i];

        di[i].clear();

        mu[i].clear();

    }

  

    return ans;

}

  
// Управляемая программа

int main()

{

    int n = 3, m = 3;

    cout << numofArray(n, m) << "\n";

    return 0;

}

Джава

// Java-программа для подсчета количества массивов
// такого размера n, что каждый элемент
// в диапазоне [1, m] и прилегающие
// делится

import java.util.*;

  

class GFG 

{

static int MAX = 1000;

  

static int numofArray(int n, int m)

{

    int [][]dp = new int[MAX][MAX];

  

    // Для хранения факторов.

    Vector<Integer> []di = new Vector[MAX];

  

    // Для хранения кратных.

    Vector<Integer> []mu = new Vector[MAX];

  

    for(int i = 0; i < MAX; i++)

    {

        for(int j = 0; j < MAX; j++)

        {

            dp[i][j] = 0;

        }

    }

    for(int i = 0; i < MAX; i++)

    {

        di[i] = new Vector<>();

        mu[i] = new Vector<>();

    }

      

    // вычисление коэффициентов и коэффициентов

    // элементов [1 ... m].

    for (int i = 1; i <= m; i++)

    {

        for (int j = 2 * i; j <= m; j += i)

        {

            di[j].add(i);

            mu[i].add(j);

        }

        di[i].add(i);

    }

  

    // Инициализация массива размера 1 для

    // каждый я <= м.

    for (int i = 1; i <= m; i++)

        dp[1][i] = 1;

  

    // Расчет количества возможных массивов

    // размера i и начинающегося с j.

    for (int i = 2; i <= n; i++)

    {

        for (int j = 1; j <= m; j++)

        {

            dp[i][j] = 0;

  

            // Для всех предыдущих возможных значений.

            // Добавление количества факторов.

            for (Integer x:di[j])

                dp[i][j] += dp[i - 1][x];

  

            // Добавляем номер кратно.

            for (Integer x:mu[j])

                dp[i][j] += dp[i - 1][x];

        }

    }

  

    // Подсчет общего количества массива

    // которые начинаются с [1 ... m].

    int ans = 0;

    for (int i = 1; i <= m; i++)

    {

        ans += dp[n][i];

        di[i].clear();

        mu[i].clear();

    }

    return ans;

}

  
// Код драйвера

public static void main(String[] args)

{

    int n = 3, m = 3;

    System.out.println(numofArray(n, m));

}
}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для подсчета количества
# массивов размера n, так что каждый элемент
# в диапазоне [1, м] и смежные делятся

  

MAX = 1000 

  

def numofArray(n, m): 

   

    dp = [[0 for i in range(MAX)] for j in range(MAX)] 

  

    # Для хранения факторов.

    di = [[] for i in range(MAX)] 

  

    # Для хранения кратных.

    mu = [[] for i in range(MAX)]

  

    # расчет факторов и коэффициентов

    Количество элементов [1 ... м].

    for i in range(1, m+1): 

       

        for j in range(2*i, m+1, i): 

           

            di[j].append(i) 

            mu[i].append(j) 

           

        di[i].append(i) 

  

    # Инициализация для массива размера 1 для каждого i <= m.

    for i in range(1, m+1): 

        dp[1][i] = 1 

  

    # Расчет количества возможных массивов

    # размера i и начиная с j.

    for i in range(2, n+1): 

       

        for j in range(1, m+1): 

           

            dp[i][j] = 0 

  

            # Для всех предыдущих возможных значений.

            # Добавление ряда факторов.

            for x in di[j]: 

                dp[i][j] += dp[i-1][x] 

  

            # Добавление номера кратно.

            for x in mu[j]: 

                dp[i][j] += dp[i-1][x] 

           

    # Расчет общего количества массивов

    # которые начинаются с [1 ... m].

    ans = 0 

    for i in range(1, m+1): 

       

        ans += dp[n][i] 

        di[i].clear() 

        mu[i].clear() 

      

    return ans 

   
# Управляемая программа

if __name__ == "__main__"

   

    n = m = 3 

    print(numofArray(n, m)) 

      
# Этот код предоставлен Rituraj Jain

C #

// C # программа для подсчета количества массивов
// такого размера n, что каждый элемент
// в диапазоне [1, m] и прилегающие
// делится

using System;

using System.Collections.Generic;                 

      

class GFG 

{

static int MAX = 1000;

  

static int numofArray(int n, int m)

{

    int [,]dp = new int[MAX, MAX];

  

    // Для хранения факторов.

    List<int> []di = new List<int>[MAX];

  

    // Для хранения кратных.

    List<int> []mu = new List<int>[MAX];

  

    for(int i = 0; i < MAX; i++)

    {

        for(int j = 0; j < MAX; j++)

        {

            dp[i, j] = 0;

        }

    }

    for(int i = 0; i < MAX; i++)

    {

        di[i] = new List<int>();

        mu[i] = new List<int>();

    }

      

    // вычисление коэффициентов и коэффициентов

    // элементов [1 ... m].

    for (int i = 1; i <= m; i++)

    {

        for (int j = 2 * i; j <= m; j += i)

        {

            di[j].Add(i);

            mu[i].Add(j);

        }

        di[i].Add(i);

    }

  

    // Инициализация массива размера 1 для

    // каждый я <= м.

    for (int i = 1; i <= m; i++)

        dp[1, i] = 1;

  

    // Расчет количества возможных массивов

    // размера i и начинающегося с j.

    for (int i = 2; i <= n; i++)

    {

        for (int j = 1; j <= m; j++)

        {

            dp[i, j] = 0;

  

            // Для всех предыдущих возможных значений.

            // Добавление количества факторов.

            foreach (int x in di[j])

                dp[i, j] += dp[i - 1, x];

  

            // Добавляем номер кратно.

            foreach (int x in mu[j])

                dp[i, j] += dp[i - 1, x];

        }

    }

  

    // Подсчет общего количества массива

    // которые начинаются с [1 ... m].

    int ans = 0;

    for (int i = 1; i <= m; i++)

    {

        ans += dp[n, i];

        di[i].Clear();

        mu[i].Clear();

    }

    return ans;

}

  
// Код драйвера

public static void Main(String[] args)

{

    int n = 3, m = 3;

    Console.WriteLine(numofArray(n, m));

}
}

  
// Этот код предоставлен Принчи Сингхом

Выход:

17

Сложность времени: O (N * M).

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Количество массивов, в которых все смежные элементы таковы, что один из них делит другой

0.00 (0%) 0 votes