C++ 统计由给定两个数字x和y组成的数字的数量，其中数字的和仅包含给定的数字x和y

问题声明包括统计由给定的两个数字x和y组成的尺寸为N的数字的数量，其中数字的和仅包含给定的数字x和y。

我们需要统计可以由x和y组成的不同数字的数量，这些数字将是尺寸为N的用户输入，其中N的范围为1到10^6。输入还会提供N的值。由尺寸为N的数字x和y组成的数字必须满足所形成数字的数字总和仅包含数字x和y。

由于N的值可能非常大，数字的数量可能非常大，所以我们需要返回以模1000000007 (即1e9+7)取余的答案。

以下示例更好地解释了该问题。

输入

x=4 , y=2  , N=2

输出

解释 - 这里给出的输入是x=4，y=2和N=2，这意味着我们需要找到包含2位数字的数字的数量。数字应该只是4和2，而且数字的位数的和应该只包含数字4和2。

满足条件的唯一可能数字是22。它包含2位数字，并由给定的数字组成，数字的位数之和等于4，即和只包含给定的数字。因此，对于此输入，答案为1。

输入

x=1 , y=3 , N=5

输出结果

解释 - 我们需要找到由数字1和3组成的大小为5的数字的计数，使得它们的数字之和只包含给定的数字。这样的数字可以是33331、33313、33133、31333、13333、33311、33113、31133、11333、13331、13313、13133、31313、31331、33131。

让我们了解一下找到使用给定数字形成的数字的计数的算法，使得它们的数字之和只包含给定的数字。

算法

给定的N的值很大，因此不可能检查每个可能的数字，以确定这些数字的数字之和是否只包含给定的数字。由于我们只需要计算由x和y组成的大小为N的数字的数量，我们只需要检查数字重复的次数。

假设x在数字中出现i次，那么y就会在数字中出现（N-i）次，因为数字仅由x和y构成，而数字的位数为N。因此，数字之和将为（x * i +（N-i）* y）。 **

如果和只包含x和y，那么我们可以使用组合数学找到使用i次x和（N-i）次y形成的数字的数量。

可以使用以下公式找到数字的计数：

$\mathrm{^NC_{i}=\frac{N!}{(N−i)!i!}or:factorial(N)modInverse(N−i)*modInverse(i)}$

该算法可以分为三个部分实现：

为了检查数字中x重复的可能次数

我们可以使用一个for循环从i=0到i<=N进行迭代，其中N是考虑数字中x重复的可能情况的所需大小。

我们可以使用公式(xi + (N-i)y)来检查每种情况下数字的和，其中i是数字中x重复的次数，范围为[0,N]。

检查数字的和是否只包含x和y作为其数字

由于使用x和y数字形成的数字的总和可以通过以下方法计算：

sum=(xi + (N-i)y) ，其中i是数字中x出现的次数，(N-i)表示数字中y出现的次数。

我们将创建一个函数来检查数字的总和。在函数中，我们将使用while循环迭代，直到总和变为0，并使用取余运算符检查总和的每个数字。

总和模10将给出数字的最后一位，因此我们将检查数字的最后一位是否等于x或y。如果最后一位等于x或y，我们将只需将数字除以10，以检查下一个数字，直到总和变为0。如果总和的每个数字都是x或y，我们将返回true。如果数字的任何一位不等于x或y，我们将返回false。

如果总和只由x和y组成，找出用i次x数字形成数字的方法数量

在检查N个位数的数字中x出现i次的每个可能值时，如果由i次x数字和(N-i)次y数字形成的数字的位数只有x和y，则我们将使用组合学计算方法计算使用i次x数字和(N-i)次y数字形成不同数字的方法数量。

寻找组成不同数字的数字中将i次x个数字排列的方式的公式是 $\mathrm{^NC_{i}=\frac{N!}{(N-i)!*i!}}$ 。由于 $\mathrm{^NC_{i}=^NC_{N-i}}$ ，因此我们可以计算其中任意一个。

$\mathrm{^NC_{i}=factorial}$

为了计算这种方式的数量，我们将预先计算阶乘和倒数阶乘的值，从0到最大值N，即10^6，并将其存储在大小为10^6+1的数组中。

可以使用以下公式计算modInverse：

modInverse(N!)= modInverse((N+1)!)*(N+1).

由于我们拥有可能的每个阶乘数值，我们将使用上述公式计算方式的数量。阶乘值可能很大，因此我们将将值存储在1e9+7的模数中。

我们将会计算使用特定数量的数字可以形成的不同数字的方式，并将它们加入答案中，进一步检查每个可能的数字位数并计算数字的数量。

我们可以使用这个算法找到由给定N个数字组成的数字的数量，这些数字的各个位数之和仅由给定数字组成。为了解决问题，我们将在我们的方法中使用这个算法。

方法

我们在实现该算法以找到数字数量的方法中需要遵循以下步骤：

我们将创建一个函数来计算使用给定数字组成的数字数量，使得数字的各位数字之和只包含给定的数字。
我们将在一个循环中迭代从i=0到i<=N，以检查每个由i个x数字和(N−i)个y数字组成的数字。
如果由i个x数字和(N−i)个y数字组成的数字的各位数字之和只包含x和y，我们将使用公式 $\mathrm{^NC_{i}}$ 计算形成N位数字的i个x数字的不同数量。

示例

//function to count the number formed by given digits whose sum having the given digit
#include <bits/stdc++.h>

using namespace std;

const int n=1000001;

const int mod=1e9+7;

//initialising array to store values of factorial and inverseFactorial till n
int fac[n]={0};
int inverseFac[n]={0};

//to calculate the inverse factorial of the last index
int lastFactorialIndex(int n,int m)
{
  int p=m;
  int a=1,b=0;
  if(m==1)
  {
      return 0;
  }
    while(n>1)
    {
      int quotient=n/m;

      int temp=m;

      m=n%m;

      n=temp;
      temp=b;

      b=a-quotient*b;

      a=temp;
    }

    if(a<0)
    {
     a=a+p; 
    }
    return a;

}

//function to store the values of factorial in the array
void factorial()
{
   fac[0]=1;

   fac[1]=1;

   for(int i=2;i<n;i++)
   {
       //since n!=n*(n-1)!
       fac[i]=(long long)fac[i-1]*i%mod;
   }


}

//function to calculate the inverse factorials for all values till n
void inverseFactorial()
{
    inverseFac[0]=1;
    inverseFac[1]=1;
    //calling the function to calculate the inverse factorial of last index
    inverseFac[n-1]=lastFactorialIndex(fac[n-1],mod);

    for(int i=n-2;i>=2;i--)
    {
        //inverse(i!)=inverse((i+1)!)*(i+1)
       inverseFac[i]=((long long)inverseFac[i+1]*(long long)(i+1)) % mod; 
    }
}

//function to check if the sum has only digits x and y
bool cal(int sum,int x,int y)
{

    if(sum==0)
    {
      return false;  
    }

    while(sum>0)
    {
        if((sum%10)!=x && (sum%10)!=y) //checking each digit of the number
        {
         return false;   
        }
        sum=sum/10;
    }
    return true;
}

//function give the number of ways of distinct numbers can be formed using i times x digit
long long int combinatorics(int n,int r)
{
    //using the formula nCr= factorial(n) * modInverse(n-r)*modInverse(r) % mod
 long long int ways= (long long)fac[n]*(long long)inverseFac[r] %mod *(long long)inverseFac[n-r]%mod;

  return ways;
}

// function to calculate count of numbers
int count_numbers(int m,int x,int y)
{
    //if both the digits are equal
    if(x==y)
    {
        if(cal(m*x,x,y)==true){
           return 1; 
        }
        else{
        return 0;
        }
    }
    int count=0;
    for(int i=0;i<=m;i++)
    {
        if(cal(i*x + (m-i)*y,x,y)) //checking for each possible case of x digit appearing i times
        {
           //if sum has the digits x and y, calculate the number of ways
            count = (count + combinatorics(m,i)) % mod; 
        }

    }
    return count;
}

int main()
{
    //calling the function to pregenerate factorials and inverse factorials
factorial();
inverseFactorial();

int m=188;
int x=8;
int y=4;
cout<<count_numbers(m,x,y);

return 0;
}