Cuente números de N dígitos posibles que consisten en dígitos X e Y

Dados tres números enteros N , X e Y , la tarea es encontrar el conteo de números de N dígitos que se pueden formar usando los dígitos del 0 al 9 que cumplan las siguientes condiciones:

• Los dígitos X e Y deben estar presentes en ellos.
• El número puede contener 0 iniciales.

Nota: Dado que la respuesta puede ser muy grande, imprima la respuesta módulo 10 ⁹ + 7 .

Ejemplos:

Entrada: N = 2, X = 1, Y = 2
Salida: 2
Explicación:
Solo hay dos números posibles 12 y 21.

Entrada: N = 10, X = 3, Y = 4  
Salida: 100172994

Enfoque: La idea es utilizar técnicas de permutación y combinación para resolver el problema. Siga los pasos a continuación para resolver el problema:

• El total de números de N dígitos que es posible usando los dígitos {0 – 9} es 10 ^N
• El total de números de N dígitos que se pueden formar usando los dígitos {0 – 9} – { X } es 9 ^N
• El total de números de N dígitos que se pueden formar usando el dígito {0 – 9} – {X, Y} es 8 ^N
• El total de números de N dígitos que contienen los dígitos X e Y es la diferencia entre todos los números posibles y los números que no contienen los dígitos X o Y seguido de la suma de los números que contienen todos los dígitos excepto X e Y. Por lo tanto, la respuesta es 10 ^N – 2 * 9 ^N + 8 ^N.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
// Function for calculate
// (x ^ y) % mod in O(log y)
long long power(int x, int y)
{
 
    // Base Condition
    if (y == 0)
        return 1;
 
    // Transition state of
    // power Function
    long long int p
        = power(x, y / 2) % mod;
 
    p = (p * p) % mod;
 
    if (y & 1) {
        p = (x * p) % mod;
    }
 
    return p;
}
 
// Function for counting total numbers
// that can be formed such that digits
// X, Y are present in each number
int TotalNumber(int N)
{
 
    // Calculate the given expression
    int ans = (power(10, N)
               - 2 * power(9, N)
               + power(8, N) + 2 * mod)
              % mod;
 
    // Return the final answer
    return ans;
}
 
// Driver Code
int main()
{
 
    int N = 10, X = 3, Y = 4;
    cout << TotalNumber(N) << endl;
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static int mod = (int)(1e9 + 7);
 
// Function for calculate
// (x ^ y) % mod in O(log y)
static long power(int x, int y)
{
 
    // Base Condition
    if (y == 0)
        return 1;
 
    // Transition state of
    // power Function
    int p = (int)(power(x, y / 2) % mod);
 
    p = (p * p) % mod;
 
    if (y % 2 == 1)
    {
        p = (x * p) % mod;
    }
    return p;
}
 
// Function for counting total numbers
// that can be formed such that digits
// X, Y are present in each number
static int TotalNumber(int N)
{
     
    // Calculate the given expression
    int ans = (int)((power(10, N) - 2 *
                     power(9, N) +
                     power(8, N) +
                        2 * mod) % mod);
 
    // Return the final answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 10, X = 3, Y = 4;
     
    System.out.print(TotalNumber(N) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
mod = 1e9 + 7
 
# Function for calculate
# (x ^ y) % mod in O(log y)
def power(x, y):
 
    # Base Condition
    if (y == 0):
        return 1
 
    # Transition state of
    # power Function
    p = power(x, y // 2) % mod
 
    p = (p * p) % mod
 
    if (y & 1):
        p = (x * p) % mod
 
    return p
 
# Function for counting total numbers
# that can be formed such that digits
# X, Y are present in each number
def TotalNumber(N):
 
    # Calculate the given expression
    ans = (power(10, N) - 2 *
           power(9, N) +
           power(8, N) + 2 * mod) % mod
 
    # Return the final answer
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    N = 10
    X = 3
    Y = 4
     
    print(TotalNumber(N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG{
 
static int mod = (int)(1e9 + 7);
 
// Function for calculate
// (x ^ y) % mod in O(log y)
static long power(int x, int y)
{
  // Base Condition
  if (y == 0)
    return 1;
 
  // Transition state of
  // power Function
  int p = (int)(power(x,
           y / 2) % mod);
 
  p = (p * p) % mod;
 
  if (y % 2 == 1)
  {
    p = (x * p) % mod;
  }
  return p;
}
 
// Function for counting
// total numbers that can be
// formed such that digits
// X, Y are present in each number
static int TotalNumber(int N)
{   
  // Calculate the given expression
  int ans = (int)((power(10, N) - 2 *
                   power(9, N) +
                   power(8, N) +
                   2 * mod) % mod);
 
  // Return the
  // readonly answer
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 10;
  Console.Write(TotalNumber(N) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript Program for the above approach
 
var mod = 1000000007;
 
// Function for calculate
// (x ^ y) % mod in O(log y)
function power(x, y)
{
 
    // Base Condition
    if (y == 0)
        return 1;
 
    // Transition state of
    // power Function
    var p
        = power(x, y / 2) % mod;
 
    p = (p * p) % mod;
 
    if (y & 1) {
        p = (x * p) % mod;
    }
 
    return p;
}
 
// Function for counting total numbers
// that can be formed such that digits
// X, Y are present in each number
function TotalNumber(N)
{
 
    // Calculate the given expression
    var ans = (power(10, N)
               - 2 * power(9, N)
               + power(8, N) + 2 * mod)
              % mod;
 
    // Return the final answer
    return ans;
}
 
// Driver Code
var N = 10, X = 3, Y = 4;
document.write( TotalNumber(N));
 
</script>

100172994

Complejidad de Tiempo: O( log N)
Espacio Auxiliar: O(1)