Dados a, b y N(1 a 10 6 ). La tarea es contar los números formados por los dígitos a y b exactamente de una longitud N tal que la suma de los dígitos del número así formado también contenga los dígitos a y b solamente. Dado que el conteo puede ser muy grande, imprima el conteo % 1000000007.
Ejemplos:
Input : a = 1 b = 3 n = 3 Output : 1 Explanation : The only number is 111 of length 3, the sum of digits of 111 is 3, which is b. Input : a = 6 b = 9 n = 1 Output : 2 Explanation : The numbers of length 1 is 6 and 9, whose sum of digits is 6 and 9 respectively which is a and b respectively. Input: a = 2 b = 3 n = 10 Output : 165
Enfoque: dado que N es muy grande, no podemos iterar todos los números para verificarlos individualmente. Como el número es de longitud N y está formado por dos dígitos a y b, a ocupará i posiciones y b ocupará n – i posiciones. La suma de dígitos será así ( a*i + (ni)*b ) . Podemos comprobar si la suma de cifras está formada por a y b para todo i comprendido entre 0 y N. Así, la cuenta total de números formados será 
la que corresponderá a toda combinación de números formada por a y b cuya suma de cifras también está formado por a y b.
Implemente operaciones modulares en los cálculos: calcule
% 1000000007 para todos los i que van de 0 a N y satisfacen la condición dada.
Una solución simple dará respuesta como:
(factorial(n) * modInverse(n - i) * modInverse(i)) % mod
Dado que el cálculo de modInverse toma O (log N), la complejidad de tiempo total será O (N log N), si todos los factoriales se calculan previamente.
Una solución eficiente será precalcular todos los factoriales hasta N. ¡Calcula la modInversa de N! en O(log N) y calcule el modInverse de todos los factoriales de (N – 1)! ¡a 1! por la fórmula dada a continuación.
modInverse(i!) = modInverse((i + 1)!) * (i + 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// 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.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1000005;
int fact[N], invfact[N];
// function to check if sum of
// digits is made of a and b
int check(int x, int a, int b)
{
// sum of digits is 0
if (x == 0)
return 0;
while (x) {
// if any of digits in sum is
// other than a and b
if (x % 10 != a and x % 10 != b)
return 0;
x /= 10;
}
return 1;
}
// calculate the modInverse V / of a number in O(log n)
int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1) {
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m, a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
// function to pregenerate factorials
void pregenFact()
{
fact[0] = fact[1] = 1;
for (int i = 1; i <= 1000000; ++i)
fact[i] = (long long)fact[i - 1] * i % mod;
}
// function to pre calculate the
// modInverse of factorials
void pregenInverse()
{
invfact[0] = invfact[1] = 1;
// calculates the modInverse of the last factorial
invfact[1000000] = modInverse(fact[1000000], mod);
// precalculates the modInverse of all factorials
// by formulae
for (int i = 999999; i > 1; --i)
invfact[i] = ((long long)invfact[i + 1] *
(long long)(i + 1)) % mod;
}
// function that returns the value of nCi
int comb(int big, int small)
{
return (long long)fact[big] * invfact[small] % mod *
invfact[big - small] % mod;
}
// function that returns the count of numbers
int count(int a, int b, int n)
{
// function call to pre-calculate the
// factorials and modInverse of factorials
pregenFact();
pregenInverse();
// if a and b are same
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;
}
// Driver Code
int main()
{
int a = 3, b = 4, n = 11028;
cout << count(a, b, n);
return 0;
}
Java
// Java 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.
class GFG
{
static int mod = (int) (1e9 + 7);
static int N = 1000005;
static int fact[] = new int[N], invfact[] = new int[N];
// function to check if sum of
// digits is made of a and b
static int check(int x, int a, int b)
{
// sum of digits is 0
if (x == 0)
{
return 0;
}
while (x > 0)
{
// if any of digits in sum is
// other than a and b
if (x % 10 != a & x % 10 != b)
{
return 0;
}
x /= 10;
}
return 1;
}
// calculate the modInverse V / of a number in O(log n)
static int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
{
return 0;
}
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
{
x += m0;
}
return x;
}
// function to pregenerate factorials
static void pregenFact()
{
fact[0] = fact[1] = 1;
for (int i = 1; i <= 1000000; ++i)
{
fact[i] = (int) ((long) fact[i - 1] * i % mod);
}
}
// function to pre calculate the
// modInverse of factorials
static void pregenInverse()
{
invfact[0] = invfact[1] = 1;
// calculates the modInverse of
// the last factorial
invfact[1000000] = modInverse(fact[1000000], mod);
// precalculates the modInverse of
// all factorials by formulae
for (int i = 999999; i > 1; --i)
{
invfact[i] = (int) (((long) invfact[i + 1]
* (long) (i + 1)) % mod);
}
}
// function that returns the value of nCi
static int comb(int big, int small)
{
return (int) ((long) fact[big] * invfact[small] % mod
* invfact[big - small] % mod);
}
// function that returns the count of numbers
static int count(int a, int b, int n)
{
// function call to pre-calculate the
// factorials and modInverse of factorials
pregenFact();
pregenInverse();
// if a and b are same
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) == 1)
{
ans = (ans + comb(n, i)) % mod;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int a = 3, b = 4, n = 11028;
System.out.println(count(a, b, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python 3 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. mod = 1000000007 N = 1000005 fact = [0] * N invfact = [0] * N # function to check if sum of # digits is made of a and b def check(x, a, b): # sum of digits is 0 if (x == 0): return 0 while (x) : # if any of digits in sum # is other than a and b if (x % 10 != a and x % 10 != b): return 0 x //= 10 return 1 # calculate the modInverse V of # a number in O(log n) def modInverse(a, m): m0 = m y = 0 x = 1 if (m == 1): return 0 while (a > 1) : # q is quotient q = a // m t = m # m is remainder now, process # same as Euclid's algo m = a % m a = t t = y # Update y and x y = x - q * y x = t # Make x positive if (x < 0): x += m0 return x # function to pregenerate factorials def pregenFact(): fact[0] = fact[1] = 1 for i in range(1, 1000001): fact[i] = fact[i - 1] * i % mod # function to pre calculate the # modInverse of factorials def pregenInverse(): invfact[0] = invfact[1] = 1 # calculates the modInverse of # the last factorial invfact[1000000] = modInverse(fact[1000000], mod) # precalculates the modInverse # of all factorials by formulae for i in range(999999, 0, -1): invfact[i] = ((invfact[i + 1] * (i + 1)) % mod) # function that returns # the value of nCi def comb(big, small): return (fact[big] * invfact[small] % mod * invfact[big - small] % mod) # function that returns the # count of numbers def count(a, b, n): # function call to pre-calculate # the factorials and modInverse # of factorials pregenFact() pregenInverse() # if a and b are same if (a == b) : return (check(a * n, a, b)) ans = 0 for i in range(n + 1) : if (check(i * a + (n - i) * b, a, b)) : ans = (ans + comb(n, i)) % mod return ans # Driver Code if __name__=="__main__": a = 3 b = 4 n = 11028 print(count(a, b, n)) # This code is contributed # by ChitraNayal
C#
// 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.
using System;
class GFG
{
static int mod = (int) (1e9 + 7);
static int N = 1000005;
static int []fact = new int[N];
static int []invfact = new int[N];
// function to check if sum of
// digits is made of a and b
static int check(int x, int a, int b)
{
// sum of digits is 0
if (x == 0)
{
return 0;
}
while (x > 0)
{
// if any of digits in sum is
// other than a and b
if (x % 10 != a & x % 10 != b)
{
return 0;
}
x /= 10;
}
return 1;
}
// calculate the modInverse V / of a number in O(log n)
static int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
{
return 0;
}
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
{
x += m0;
}
return x;
}
// function to pregenerate factorials
static void pregenFact()
{
fact[0] = fact[1] = 1;
for (int i = 1; i <= 1000000; ++i)
{
fact[i] = (int) ((long) fact[i - 1] * i % mod);
}
}
// function to pre calculate the
// modInverse of factorials
static void pregenInverse()
{
invfact[0] = invfact[1] = 1;
// calculates the modInverse of
// the last factorial
invfact[1000000] = modInverse(fact[1000000], mod);
// precalculates the modInverse of
// all factorials by formulae
for (int i = 999999; i > 1; --i)
{
invfact[i] = (int) (((long) invfact[i + 1]
* (long) (i + 1)) % mod);
}
}
// function that returns the value of nCi
static int comb(int big, int small)
{
return (int) ((long) fact[big] * invfact[small] % mod
* invfact[big - small] % mod);
}
// function that returns the count of numbers
static int count(int a, int b, int n)
{
// function call to pre-calculate the
// factorials and modInverse of factorials
pregenFact();
pregenInverse();
// if a and b are same
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) == 1)
{
ans = (ans + comb(n, i)) % mod;
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int a = 3, b = 4, n = 11028;
Console.WriteLine(count(a, b, n));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript 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.
const mod = 1000000007;
const N = 1000005;
let fact = new Array(N).fill(0);
let invfact = new Array(N).fill(0);
// function to check if sum of
// digits is made of a and b
const check = (x, a, b) => {
// sum of digits is 0
if (x == 0)
return 0;
while (x) {
// if any of digits in sum is
// other than a and b
if (x % 10 != a && x % 10 != b)
return 0;
x = Math.floor(x / 10);
}
return 1;
}
// calculate the modInverse V / of a number in O(log n)
const modInverse = (a, m) => {
let m0 = m;
let y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1) {
// q is quotient
let q = Math.floor(a / m);
let t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
// function to pregenerate factorials
const pregenFact = () => {
fact[0] = 1;
fact[1] = 1;
for (let i = 1; i <= 1000000; ++i)
fact[i] = fact[i - 1] * i % mod;
}
// function to pre calculate the
// modInverse of factorials
const pregenInverse = () => {
invfact[0] = 1;
invfact[1] = 1;
// calculates the modInverse of the last factorial
invfact[1000000] = modInverse(fact[1000000], mod);
// precalculates the modInverse of all factorials
// by formulae
for (let i = 999999; i > 1; --i)
invfact[i] = (invfact[i + 1] * (i + 1)) % mod;
}
// function that returns the value of nCi
let comb = (big, small) => {
return ((BigInt(fact[big]) * BigInt(invfact[small])) % BigInt(mod) * BigInt(invfact[big - small]) % BigInt(mod)) % BigInt(mod);
}
// function that returns the count of numbers
const count = (a, b, n) => {
// function call to pre-calculate the
// factorials and modInverse of factorials
pregenFact();
pregenInverse();
// if a and b are same
if (a == b)
return (check(a * n, a, b));
let ans = 0n;
for (let i = 0; i <= n; ++i)
if (check(i * a + (n - i) * b, a, b)) {
ans = (ans + comb(n, i)) % BigInt(mod);
}
return ans;
}
// Driver Code
let a = 3, b = 4, n = 11028;
document.write(count(a, b, n));
// This code is contributed by rakeshsahni
</script>
Producción:
461668105