Count of arrays in which all adjacent elements are such that one of them divide the another | Python3 program to count the number of arrays of size n such that every element is in range [ 1 , m ] and adjacent are divisible ; For storing factors . ; For storing multiples . ; calculating the factors and multiples of elements [ 1. . . m ] . ; Initialising for size 1 array for each i <= m . ; Calculating the number of array possible of size i and starting with j . ; For all previous possible values . Adding number of factors . ; Adding number of multiple . ; Calculating the total count of array which start from [ 1. . . m ] . ; Driven Program
MAX = 1000 NEW_LINE def numofArray ( n , m ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( MAX ) ] for j in range ( MAX ) ] NEW_LINE di = [ [ ] for i in range ( MAX ) ] NEW_LINE mu = [ [ ] for i in range ( MAX ) ] NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT for j in range ( 2 * i , m + 1 , i ) : NEW_LINE INDENT di [ j ] . append ( i ) NEW_LINE mu [ i ] . append ( j ) NEW_LINE DEDENT di [ i ] . append ( i ) NEW_LINE DEDENT for i in range ( 1 , m + 1 ) : NEW_LINE INDENT dp [ 1 ] [ i ] = 1 NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE for x in di [ j ] : NEW_LINE INDENT dp [ i ] [ j ] += dp [ i - 1 ] [ x ] NEW_LINE DEDENT for x in mu [ j ] : NEW_LINE INDENT dp [ i ] [ j ] += dp [ i - 1 ] [ x ] NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT ans += dp [ n ] [ i ] NEW_LINE di [ i ] . clear ( ) NEW_LINE mu [ i ] . clear ( ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = m = 3 NEW_LINE print ( numofArray ( n , m ) ) NEW_LINE DEDENT