資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學由給定兩位數和給定數字之和構成的數字計數
題目描述包括計算由給定的兩位數 x 和 y 構成的 N 位數，其各位數字之和僅包含給定的數字 x 和 y。
我們需要計算可以使用數字 x 和 y（使用者輸入，大小為 N，N 的範圍為 1 到 10^6）構成的不同數字的數量。N 也將作為輸入提供。使用數字 x 和 y 構成的 N 位數必須滿足其各位數字之和只包含數字 x 和 y。
由於 N 的值可能很大，數字的計數也可能很大，因此我們需要將答案以模 1000000007（即 1e9+7）的形式返回。
下面的例子可以更好地理解這個問題。
輸入
x=4 , y=2 , N=2
輸出
1
解釋− 此處給定的輸入是 x=4，y=2，N=2，這意味著我們需要找到包含 2 位數字的數字個數。這些數字只能是 4 和 2，並且該數字的各位數字之和必須只包含給定的數字。
滿足條件的唯一可能的數字是 22。它包含 2 位數字，由給定的數字構成，並且數字的各位數字之和等於 4，即和只包含給定的數字。因此，對於此輸入，所需答案為 1。
輸入
x=1 , y=3 , N=5
輸出
15
解釋− 我們需要找到使用數字 1 和 3 構成 5 位數的個數，其各位數字之和必須只包含給定的數字。
33331, 33313, 33133, 31333, 13333, 33311, 33113, 31133, 11333, 13331, 13313, 13133, 31313, 31331, 33131.
讓我們瞭解一下演算法，以查詢使用給定數字構成的數字個數，其各位數字之和只包含給定的數字。
演算法
給定的 N 值很大，因此如果這些數字的各位數字之和只包含給定的數字，則不可能檢查每個可能的數字。因為我們只需要計算由 N 位數字 x 和 y 構成的數字個數，所以我們可以簡單地檢查數字 x 在所構成的數字中重複的次數。
假設 x 在數字中出現 i 次，那麼由於該數字僅由數字 x 和 y 構成，並且數字中的位數為 N，因此 y 將在數字中出現 (N−i) 次。因此，數字的和將為 (x*i + (N−i)*y)。
如果和只包含 x 和 y，那麼我們可以使用組合數學計算使用 i 次 x 和 (N−i) 次 y 構成的數字個數。
可以使用以下公式計算數字的個數
$\mathrm{^NC_{i}=\frac{N!}{(N−i)!*i!}或\: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，並使用模運算子檢查和的每一位數字。
sum 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 數字構成 N 位不同數字的方法數。
計算在數字中排列 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 作為其數字，我們將使用公式 $\mathrm{^NC_{i}}$ 計算我們可以使用 i 次 x 數字構成 N 位不同數字的方法數。
示例
//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;
}
輸出
917113677
時間複雜度− O(n*logn)
空間複雜度− O(n)，因為我們使用了大小為 n 的陣列來儲存階乘和逆階乘的值。
結論
本文討論了確定可以使用給定的兩位數生成的數字個數的問題，其數字的各位數字之和只包含數字 x 和 y。我們使用了組合數學原理來確定數字的總數，而不是檢查每個數字。對有效的 C++ 解決方案進行了詳細解釋。
閱讀完這篇文章後，我希望您對這個問題和解決方案有更好的理解。
瀏覽量 106 次
