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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int calculate ( int position , int used , int unused , int P , int M , vector < vector < vector < 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 ; } int solve ( int N , int P , int M ) { vector < vector < vector < int > > > dp ( 101 , vector < vector < int > > ( 101 , vector < int > ( 101 , -1 ) ) ) ; return calculate ( 0 , 0 , N , P , M , dp ) ; } int main ( ) { int N = 2 , M = 0 , P = 3 ; cout << solve ( N , P , M ) ; }