Count of N | Function to calculate the total count of N - digit numbers such that the sum of digits at even positions and odd positions are divisible by A and B respectively ; For single digit numbers ; Largest possible number ; Count of possible odd digits ; Count of possible even digits ; Calculate total count of sequences of length even_count with sum divisible by A where first digit can be zero ; Calculate total count of sequences of length odd_count with sum divisible by B where cannot be zero ; Return their product as answer ; Driver Code
def count ( N , A , B ) : NEW_LINE INDENT if ( N == 1 ) : NEW_LINE INDENT return 9 // B + 1 NEW_LINE DEDENT max_sum = 9 * N NEW_LINE odd_count = N // 2 + N % 2 NEW_LINE even_count = N - odd_count NEW_LINE dp = [ [ 0 for x in range ( max_sum + 1 ) ] for y in range ( even_count ) ] NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT dp [ 0 ] [ i % A ] += 1 NEW_LINE DEDENT for i in range ( 1 , even_count ) : NEW_LINE INDENT for j in range ( 10 ) : NEW_LINE INDENT for k in range ( max_sum + 1 ) : NEW_LINE INDENT if ( dp [ i - 1 ] [ k ] > 0 ) : NEW_LINE INDENT dp [ i ] [ ( j + k ) % A ] += dp [ i - 1 ] [ k ] NEW_LINE DEDENT DEDENT DEDENT DEDENT dp1 = [ [ 0 for x in range ( max_sum ) ] for y in range ( odd_count ) ] NEW_LINE for i in range ( 1 , 10 ) : NEW_LINE INDENT dp1 [ 0 ] [ i % B ] += 1 NEW_LINE DEDENT for i in range ( 1 , odd_count ) : NEW_LINE INDENT for j in range ( 10 ) : NEW_LINE INDENT for k in range ( max_sum + 1 ) : NEW_LINE INDENT if ( dp1 [ i - 1 ] [ k ] > 0 ) : NEW_LINE INDENT dp1 [ i ] [ ( j + k ) % B ] += dp1 [ i - 1 ] [ k ] NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp [ even_count - 1 ] [ 0 ] * dp1 [ odd_count - 1 ] [ 0 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 2 NEW_LINE A = 2 NEW_LINE B = 5 NEW_LINE print ( count ( N , A , B ) ) NEW_LINE DEDENT