Count of valid arrays of size P with elements in range [ 1 , N ] having duplicates at least M distance apart | Function to calculate the total number of arrays ; If the size of the array is P ; Check if all elements are used atlease once ; Check if this state is already calculated ; Initialize the result ; Use a number from the list of unused numbers ; There are ' unused ' number of favourable choices ; Use a number from already present number atlease M distance back ; There are ' used ▁ - ▁ M ' number of favourable choices ; Store the result ; Function to solve the problem ; Initialize DP table : dp [ i ] [ j ] [ j ] i : current position / index j : number of used elements k : number of unused elements ; Driver Code
def calculate ( position , used , unused , P , M , dp ) : NEW_LINE INDENT if ( position == P ) : NEW_LINE INDENT if unused == 0 : NEW_LINE return 1 NEW_LINE else : NEW_LINE return 0 NEW_LINE DEDENT if ( dp [ position ] [ used ] [ unused ] != - 1 ) : NEW_LINE INDENT return dp [ position ] [ used ] [ unused ] NEW_LINE DEDENT result = 0 NEW_LINE if ( unused > 0 ) : NEW_LINE INDENT result += calculate ( position + 1 , used + 1 , unused - 1 , P , M , dp ) * unused NEW_LINE DEDENT if ( used > M ) : NEW_LINE INDENT result += calculate ( position + 1 , used , unused , P , M , dp ) * ( used - M ) NEW_LINE DEDENT dp [ position ] [ used ] [ unused ] = result NEW_LINE return dp [ position ] [ used ] [ unused ] NEW_LINE DEDENT def solve ( N , P , M ) : NEW_LINE INDENT dp = [ [ [ - 1 for i in range ( 101 ) ] for i in range ( 101 ) ] for j in range ( 101 ) ] NEW_LINE return calculate ( 0 , 0 , N , P , M , dp ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE M = 0 NEW_LINE P = 3 NEW_LINE print ( solve ( N , P , M ) ) NEW_LINE DEDENT