计算由给定两位数字组成的数字，其和具有给定数字
问题陈述包括计算由给定两位数字 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
输出
1
解释− 这里给出的输入是 x=4,y=2 和 N=2，这意味着我们需要找到包含 2 位数字的数字的数量。数字只能是 4 和 2，并且数字的位数之和只能包含数字 4 和 2。
唯一可能满足条件的数字是 22。它包含 2 位数字，由给定的数字组成，数字的位数之和等于 4，即数字之和仅包含给定的数字。因此，1 是此输入的必需答案。
输入
x=1 , y=3 , N=5
输出
15
解释 − 我们需要找到使用大小为 5 的数字 1 和 3 形成的数字的数量，使得它们的数字总和应该只包含给定的数字。这样的数字可以是，
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 重复次数的所有可能情况。
我们可以使用公式 (x*i + (N−i)*y) 检查每种情况的数字总和，其中 i 是数字中 x 重复的次数，范围从[0,N]。
检查数字的总和是否仅包含 x 和 y 作为其数字
由于使用 x 和 y 数字形成的数字的总和可以按以下方式计算:
sum=(x*i + (N−i)*y)，其中 i 是 x 出现在数字中的次数，(N−i) 表示 y 出现在数字中的次数。
我们将创建一个函数来检查数字的总和。在函数中，我们将在 while 循环中迭代，直到总和变为 0，并使用模数运算符检查总和的每一位数字。
总和 mod 10 将给出数字的最后一位数字，因此我们将检查数字的最后一位数字是否等于 x 或 y。如果它等于 x 或 y，我们将用 10 除以该数字以检查下一位数字，直到和为 0。如果和的每个数字都是 x 或 y，则我们将返回 true。如果数字的任何一位不等于 x 或 y，我们将返回 false。
如果和只有 x 和 y 位数字，则找出使用 i 乘以 x 位数字形成数字的方法数
在检查 i 的每个可能值时，其中 i 表示 x 在 N- 大小的数字中出现的次数，如果由 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 个数字形成的数字的数量，使得形成的数字的数字之和只有给定的数字。我们将使用我们的方法中的算法来解决问题。
方法
在我们的方法中，实现算法以查找数字数量需要遵循的步骤如下:
我们将创建一个函数来计算使用给定数字形成的数字，使得数字之和仅具有给定的数字。
我们将在 for 循环中从 i=0 到 i<=N 进行迭代，以检查每个具有 i 乘以 x 数字和 (N-i) 乘以 y 数字的数字。
如果具有 i 乘以 x 和 (N-i) 乘以 y 数字的数字之和仅包含 x 和 y 作为其数字，我们将使用公式计算我们可以形成具有 i 乘以 x 数字的大小为 N 的不同数字的方法数$\mathrm{^NC_{i}}$
示例
//函数用于计算由给定数字组成的数字，这些数字的总和具有给定数字
#include <bits/stdc++.h>
using namespace std;
const int n=1000001;
const int mod=1e9+7;
//初始化数组以存储直到 n 的阶乘和逆阶乘的值
int fac[n]={0};
int inverseFac[n]={0};
//计算最后一个索引的逆阶乘
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;
}
//函数将阶乘的值存储在数组中
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;
}
}
// 函数用于计算直到 n 的所有值的逆阶乘
void inverseFactorial()
{
inverseFac[0]=1;
inverseFac[1]=1;
// 调用函数计算最后一个索引的逆阶乘
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;
}
}
// 函数用于检查总和是否只有数字 x 和 y
bool cal(int sum,int x,int y)
{
if(sum==0)
{
return false;
}
while(sum>0)
{
if((sum%10)!=x && (sum%10)!=y) //检查数字的每一位数字
{
return false;
}
sum=sum/10;
}
return true;
}
//函数给出使用 i 乘以 x 位可以形成不同数字的方式数
long long int combinatorics(int n,int r)
{
//使用公式 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;
}
// 函数用于计算数字的数量
int count_numbers(int m,int x,int y)
{
//如果两个数字相等
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)) //检查 x 数字出现 i 次的每种可能情况
{
//如果总和包含数字 x 和 y，则计算方法的数量
count = (count + combinatorics(m,i)) % mod;
}
}
return count;
}
int main()
{
//调用函数预生成阶乘和逆阶乘
factorial();
inverseFactorial();
int m=188;
int x=8;
int y=4;
cout<<count_numbers(m,x,y);
return 0;
}
输出
917113677
时间复杂度− O(n*logn)
空间复杂度− O(n) ，因为我们使用大小为 n 的数组来存储阶乘和逆阶乘的值。
结论
本文讨论了确定使用提供的两个数字可能生成的数字数量的问题，使得数字的数字总和仅包含数字 x 和 y。我们没有检查每个数字，而是使用组合原理来确定数字的总数。有效的 C++ 解决方案已得到彻底解释。
阅读这篇文章后，我希望您对问题和解决方案有更好的理解。
