Count of N | Store the recurring recursive states ; Function to find the number of strings of length N such that it is a concatenation it substrings ; Single character cant be repeated ; Check if this state has been already calculated ; Stores the resultant count for the current recursive calls ; Iterate over all divisors ; Non - Repeated = Total - Repeated ; Non - Repeated = Total - Repeated ; Store the result for the further calculation ; Return resultant count ; Driver Code ; Function Call
dp = { } NEW_LINE def countStrings ( N ) : NEW_LINE INDENT if N == 1 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp . get ( N , - 1 ) != - 1 : NEW_LINE INDENT return dp [ N ] NEW_LINE DEDENT ret = 0 NEW_LINE for div in range ( 1 , int ( N ** .5 ) + 1 ) : NEW_LINE INDENT if N % div == 0 : NEW_LINE INDENT ret += ( 1 << div ) - countStrings ( div ) NEW_LINE div2 = N // div NEW_LINE if div2 != div and div != 1 : NEW_LINE INDENT ret += ( 1 << div2 ) - countStrings ( div2 ) NEW_LINE DEDENT DEDENT DEDENT dp [ N ] = ret NEW_LINE return ret NEW_LINE DEDENT N = 6 NEW_LINE print ( countStrings ( N ) ) NEW_LINE