Count different numbers possible using all the digits their frequency times | C ++ implementation of the above approach ; Initialize an array to store factorial values ; Function to calculate and store X ! values ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; x = x % p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Function that return modular inverse of x under modulo p ; Function that returns the count of different number possible by using all the digits its frequency times ; Preprocess factorial values ; Initialize the result and sum of aint the frequencies ; Calculate the sum of frequencies ; Putting res equal to x ! ; Multiplying res with modular inverse of X0 ! , X1 ! , . . , X9 ! ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE #define MAXN  100000 NEW_LINE #define MOD  1000000007 NEW_LINE ll fact [ MAXN ] ; void factorial ( ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < MAXN ; i ++ ) fact [ i ] = ( fact [ i - 1 ] * i ) % MOD ; } ll power ( ll x , ll y , ll p ) { while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } ll modInverse ( ll x , ll p ) { return power ( x , p - 2 , p ) ; } ll countDifferentNumbers ( ll arr [ ] , ll P ) { factorial ( ) ; ll res = 0 , X = 0 ; for ( int i = 0 ; i < 10 ; i ++ ) X += arr [ i ] ; res = fact [ X ] ; for ( int i = 0 ; i < 10 ; i ++ ) { if ( arr [ i ] > 1 ) res = ( res * modInverse ( fact [ arr [ i ] ] , P ) ) % P ; } return res ; } int main ( ) { ll arr [ ] = { 1 , 0 , 2 , 0 , 0 , 7 , 4 , 0 , 0 , 3 } ; cout << countDifferentNumbers ( arr , MOD ) ; return 0 ; }