Count numbers formed by given two digit with sum having given digits | Python 3 program to count the number of numbers formed by digits a and b exactly of a length N such that the sum of the digits of the number thus formed is of digits a and b . ; function to check if sum of digits is made of a and b ; sum of digits is 0 ; if any of digits in sum is other than a and b ; calculate the modInverse V of a number in O ( log n ) ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Update y and x ; Make x positive ; function to pregenerate factorials ; function to pre calculate the modInverse of factorials ; calculates the modInverse of the last factorial ; precalculates the modInverse of all factorials by formulae ; function that returns the value of nCi ; function that returns the count of numbers ; function call to pre - calculate the factorials and modInverse of factorials ; if a and b are same ; Driver Code
mod = 1000000007 NEW_LINE N = 1000005 NEW_LINE fact = [ 0 ] * N NEW_LINE invfact = [ 0 ] * N NEW_LINE def check ( x , a , b ) : NEW_LINE INDENT if ( x == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( x ) : NEW_LINE INDENT if ( x % 10 != a and x % 10 != b ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT x //= 10 NEW_LINE DEDENT return 1 NEW_LINE DEDENT def modInverse ( a , m ) : NEW_LINE INDENT m0 = m NEW_LINE y = 0 NEW_LINE x = 1 NEW_LINE if ( m == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( a > 1 ) : NEW_LINE INDENT q = a // m NEW_LINE t = m NEW_LINE m = a % m NEW_LINE a = t NEW_LINE t = y NEW_LINE y = x - q * y NEW_LINE x = t NEW_LINE DEDENT if ( x < 0 ) : NEW_LINE INDENT x += m0 NEW_LINE DEDENT return x NEW_LINE DEDENT def pregenFact ( ) : NEW_LINE INDENT fact [ 0 ] = fact [ 1 ] = 1 NEW_LINE for i in range ( 1 , 1000001 ) : NEW_LINE INDENT fact [ i ] = fact [ i - 1 ] * i % mod NEW_LINE DEDENT DEDENT def pregenInverse ( ) : NEW_LINE INDENT invfact [ 0 ] = invfact [ 1 ] = 1 NEW_LINE invfact [ 1000000 ] = modInverse ( fact [ 1000000 ] , mod ) NEW_LINE for i in range ( 999999 , 0 , - 1 ) : NEW_LINE INDENT invfact [ i ] = ( ( invfact [ i + 1 ] * ( i + 1 ) ) % mod ) NEW_LINE DEDENT DEDENT def comb ( big , small ) : NEW_LINE INDENT return ( fact [ big ] * invfact [ small ] % mod * invfact [ big - small ] % mod ) NEW_LINE DEDENT def count ( a , b , n ) : NEW_LINE INDENT pregenFact ( ) NEW_LINE pregenInverse ( ) NEW_LINE if ( a == b ) : NEW_LINE INDENT return ( check ( a * n , a , b ) ) NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT if ( check ( i * a + ( n - i ) * b , a , b ) ) : NEW_LINE INDENT ans = ( ans + comb ( n , i ) ) % mod NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = 3 NEW_LINE b = 4 NEW_LINE n = 11028 NEW_LINE print ( count ( a , b , n ) ) NEW_LINE DEDENT