Count of distinct numbers formed by shuffling the digits of a large number N | C ++ program for the above approach ; Recursive function to return the value of ( x ^ n ) % m ; Base Case ; If N is even ; Else N is odd ; Function to find modular inverse of a number x under modulo m ; Using Fermat 's little theorem ; Function to count of numbers formed by shuffling the digits of a large number N ; Modulo value ; Array to store the factorials upto the maximum value of N ; Store factorial of i at index i ; To store count of occurrence of a digit ; Increment the count of digit occured ; Assign the factorial of length of input ; Multiplying result with the modulo multiplicative inverse of factorial of count of i ; Print the result ; Driver Code ; Given Number as string ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE ll modexp ( ll x , ll n , ll m ) { if ( n == 0 ) { return 1 ; } else if ( n % 2 == 0 ) { return modexp ( ( x * x ) % m , n / 2 , m ) ; } else { return ( x * modexp ( ( x * x ) % m , ( n - 1 ) / 2 , m ) % m ) ; } } ll modInverse ( ll x , ll m ) { return modexp ( x , m - 2 , m ) ; } void countNumbers ( string N ) { ll m = 1000000007 ; ll factorial [ 100001 ] ; factorial [ 0 ] = 1 ; for ( ll i = 1 ; i < 100001 ; i ++ ) { factorial [ i ] = ( factorial [ i - 1 ] * i ) % m ; } ll count [ 10 ] ; for ( ll i = 0 ; i < 10 ; i ++ ) { count [ i ] = 0 ; } ll length = N . length ( ) ; for ( ll i = 0 ; i < length ; i ++ ) count [ N [ i ] - '0' ] ++ ; ll result = factorial [ length ] ; for ( ll i = 0 ; i < 10 ; i ++ ) { result = ( result * modInverse ( factorial [ count [ i ] ] , m ) ) % m ; } cout << result ; } int main ( ) { string N = "0223" ; countNumbers ( N ) ; return 0 ; }