Count of valid arrays of size P with elements in range [ 1 , N ] having duplicates at least M distance apart | C # program for the above approach ; 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
using System ; public class GFG { static int calculate ( int position , int used , int unused , int P , int M , int [ , , ] dp ) { if ( position == P ) { return unused == 0 ? 1 : 0 ; } if ( dp [ position , used , unused ] != - 1 ) return dp [ position , used , unused ] ; int result = 0 ; if ( unused > 0 ) { result += calculate ( position + 1 , used + 1 , unused - 1 , P , M , dp ) * unused ; } if ( used > M ) { result += calculate ( position + 1 , used , unused , P , M , dp ) * ( used - M ) ; } return dp [ position , used , unused ] = result ; } static int solve ( int N , int P , int M ) { int [ , , ] dp = new int [ 101 , 101 , 101 ] ; for ( int i = 0 ; i < 101 ; i ++ ) { for ( int j = 0 ; j < 101 ; j ++ ) for ( int k = 0 ; k < 101 ; k ++ ) dp [ i , j , k ] = - 1 ; } return calculate ( 0 , 0 , N , P , M , dp ) ; } public static void Main ( String [ ] args ) { int N = 2 , M = 0 , P = 3 ; Console . WriteLine ( solve ( N , P , M ) ) ; } }