Contar diferentes números posibles usando todos los dígitos por su frecuencia

Dada una array arr[] que contiene la frecuencia de los dígitos (0-9), la tarea es encontrar el conteo de números posible usando cada dígito por su frecuencia. Es decir, los números finales generados deben contener todos los dígitos multiplicados por su frecuencia. Dado que el recuento puede ser muy grande, devuelva la respuesta módulo 10^9+7. Prerrequisitos: Factorial de un número , Inverso multiplicativo modular Ejemplos:

Input : arr[] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0}
Output : 2
Frequency of 1 and 2 is 1 and all the rest is 0. 
Therefore, 2 possible numbers are 12 and 21.

Input : arr[] = {0, 5, 2, 0, 0, 0, 4, 0, 1, 1}
Output : 1081080

Enfoque : el problema se puede resolver fácilmente usando permutaciones y combinaciones. El i-ésimo índice de la array arr[] da la frecuencia del i-ésimo dígito. Se puede pensar en el problema como encontrar la permutación total de objetos X donde los objetos X0 son de un tipo, los objetos X1 son de otro tipo y así sucesivamente. Entonces la posible cuenta de números está dada por:

Recuento total = X! / (¡X0! * ¡X1! *…..* ¡X9!)

donde X = Suma de las frecuencias de todos los dígitos y Xi = la frecuencia del i-ésimo dígito. A continuación se muestra la implementación del enfoque anterior. 

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

// Java program to implement
// the above approach
class GFG
{
 
static int MAXN = 100000;
static int MOD = 1000000007;
 
// Initialize an array to store factorial values
static long fact[] = new long[MAXN];
 
// Function to calculate and store X! values
static void factorial()
{
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
}
 
// Iterative Function to calculate (x^y)%p in O(log y)
static long power(long x, long y, long p)
{
    long res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y % 2== 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Function that return modular
// inverse of x under modulo p
static long modInverse(long x, long p)
{
    return power(x, p - 2, p);
}
 
// Function that returns the count of
// different number possible by using
// along the digits its frequency times
static long countDifferentNumbers(long arr[], long P)
{
    // Preprocess factorial values
    factorial();
 
    // Initialize the result and sum
    // of aint the frequencies
    long res = 0, X = 0;
 
    // Calculate the sum of frequencies
    for (int i = 0; i < 10; i++)
        X += arr[i];
 
    // Putting res equal to x!
    res = fact[(int)X];
 
    // Multiplying res with modular
    // inverse of X0!, X1!, .., X9!
    for (int i = 0; i < 10; i++)
    {
        if (arr[i] > 1)
            res = (res * modInverse(fact[(int)arr[i]], P)) % P;
    }
 
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    long arr[] = { 1, 0, 2, 0, 0, 7, 4, 0, 0, 3 };
    System.out.println(countDifferentNumbers(arr, MOD));
}
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the above approach
MAXN = 100000
MOD = 1000000007
 
# Initialize an array to store
# factorial values
fact = [0] * MAXN;
 
# Function to calculate and store X! values
def factorial() :
    fact[0] = 1
    for i in range(1, MAXN) :
        fact[i] = (fact[i - 1] * i) % MOD
 
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p) :
 
    res = 1 # Initialize result
 
    x = x % p # Update x if it is more than 
              # or equal to p
 
    while (y > 0) :
         
        # If y is odd, multiply x with result
        if (y & 1) :
            res = (res * x) % p
 
        # y must be even now
        y = y >> 1; # y = y/2
        x = (x * x) % p
     
    return res
 
# Function that return modular
# inverse of x under modulo p
def modInverse(x, p) :
    return power(x, p - 2, p)
 
# Function that returns the count of
# different number possible by using
# all the digits its frequency times
def countDifferentNumbers(arr, P) :
 
    # Preprocess factorial values
    factorial();
 
    # Initialize the result and sum
    # of aint the frequencies
    res = 0; X = 0;
 
    # Calculate the sum of frequencies
    for i in range(10) :
        X += arr[i]
 
    # Putting res equal to x!
    res = fact[X]
 
    # Multiplying res with modular
    # inverse of X0!, X1!, .., X9!
    for i in range(10) :
        if (arr[i] > 1) :
            res = (res * modInverse(fact[arr[i]], P)) % P;
 
    return res;
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [1, 0, 2, 0, 0, 7, 4, 0, 0, 3 ]
    print(countDifferentNumbers(arr, MOD))
     
# This code is contributed by Ryuga

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
    static int MAXN = 100000;
    static int MOD = 1000000007;
     
    // Initialize an array to store factorial values
    static long []fact = new long[MAXN];
     
    // Function to calculate and store X! values
    static void factorial()
    {
        fact[0] = 1;
        for (int i = 1; i < MAXN; i++)
            fact[i] = (fact[i - 1] * i) % MOD;
    }
     
    // Iterative Function to calculate (x^y)%p in O(log y)
    static long power(long x, long y, long p)
    {
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        while (y > 0)
        {
            // If y is odd, multiply x with result
            if (y % 2== 1)
                res = (res * x) % p;
     
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
     
    // Function that return modular
    // inverse of x under modulo p
    static long modInverse(long x, long p)
    {
        return power(x, p - 2, p);
    }
     
    // Function that returns the count of
    // different number possible by using
    // along the digits its frequency times
    static long countDifferentNumbers(long []arr, long P)
    {
        // Preprocess factorial values
        factorial();
     
        // Initialize the result and sum
        // of aint the frequencies
        long res = 0, X = 0;
     
        // Calculate the sum of frequencies
        for (int i = 0; i < 10; i++)
            X += arr[i];
     
        // Putting res equal to x!
        res = fact[(int)X];
     
        // Multiplying res with modular
        // inverse of X0!, X1!, .., X9!
        for (int i = 0; i < 10; i++)
        {
            if (arr[i] > 1)
                res = (res * modInverse(fact[(int)arr[i]], P)) % P;
        }
     
        return res;
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
        long []arr = { 1, 0, 2, 0, 0, 7, 4, 0, 0, 3 };
        Console.WriteLine(countDifferentNumbers(arr, MOD));
    }
}
 
// This code has been contributed by 29AjayKumar

245044800

Complejidad de tiempo: O (MAXN)

Espacio Auxiliar: O(MAXN)