Count numbers formed by given two digit with sum having given digits | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int mod = 1e9 + 7 ; const int N = 1000005 ; int fact [ N ] , invfact [ N ] ; int check ( int x , int a , int b ) { if ( x == 0 ) return 0 ; while ( x ) { if ( x % 10 != a and x % 10 != b ) return 0 ; x /= 10 ; } return 1 ; } int modInverse ( int a , int m ) { int m0 = m ; int y = 0 , x = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { int q = a / m ; int t = m ; m = a % m , a = t ; t = y ; y = x - q * y ; x = t ; } if ( x < 0 ) x += m0 ; return x ; } void pregenFact ( ) { fact [ 0 ] = fact [ 1 ] = 1 ; for ( int i = 1 ; i <= 1000000 ; ++ i ) fact [ i ] = ( long long ) fact [ i - 1 ] * i % mod ; } void pregenInverse ( ) { invfact [ 0 ] = invfact [ 1 ] = 1 ; invfact [ 1000000 ] = modInverse ( fact [ 1000000 ] , mod ) ; for ( int i = 999999 ; i > 1 ; -- i ) invfact [ i ] = ( ( long long ) invfact [ i + 1 ] * ( long long ) ( i + 1 ) ) % mod ; } int comb ( int big , int small ) { return ( long long ) fact [ big ] * invfact [ small ] % mod * invfact [ big - small ] % mod ; } int count ( int a , int b , int n ) { pregenFact ( ) ; pregenInverse ( ) ; if ( a == b ) return ( check ( a * n , a , b ) ) ; int ans = 0 ; for ( int i = 0 ; i <= n ; ++ i ) if ( check ( i * a + ( n - i ) * b , a , b ) ) ans = ( ans + comb ( n , i ) ) % mod ; return ans ; } int main ( ) { int a = 3 , b = 4 , n = 11028 ; cout << count ( a , b , n ) ; return 0 ; }