If the number of digits to form is less than the number of digits in C, then any number of length B using the digits in A is valid (with care for leading zeros).
When the number of digits to form is equal to the number of digits in C, we need to count only those numbers less than C. We use digit DP to count valid numbers position by position.
classSolution {
public:int solve(vector<int>&A, int B, int C) {
string S = to_string(C);
int d = A.size(), n = S.size();
if (d ==0|| B > n) return0;
if (B < n) {
if (A[0] ==0&& B >1) return (d-1) * pow(d, B-1);
returnpow(d, B);
}
vector<int> digits;
for (char c : S) digits.push_back(c -'0');
vector<int> lower(11, 0);
for (int x : A) lower[x+1] =1;
for (int i =1; i <=10; i++) lower[i] += lower[i-1];
int dp =0, flag =1;
for (int i =0; i < B; i++) {
int dgt = digits[i];
int cnt = lower[dgt];
if (i ==0&& A[0] ==0&& B >1) cnt--;
dp = dp * d + flag * cnt;
flag = flag && (lower[dgt+1] == lower[dgt] +1);
}
return dp;
}
};
classSolution {
publicintsolve(ArrayList<Integer> A, int B, int C) {
char[] ca = Integer.toString(C).toCharArray();
if (A.size() == 0 || B > ca.length) return 0;
if (B < ca.length) {
if (A.get(0) == 0 && B > 1) return (int)Math.pow(A.size()-1, 1) * (int)Math.pow(A.size(), B-1);
return (int)Math.pow(A.size(), B);
}
int[] lower =newint[11];
for (int x : A) lower[x+1]= 1;
for (int i = 1; i <= 10; i++) lower[i]+= lower[i-1];
int dp = 0, flag = 1;
for (int i = 0; i < B; i++) {
int dgt = ca[i]-'0';
int cnt = lower[dgt];
if (i == 0 && A.get(0) == 0 && B > 1) cnt--;
dp = dp * A.size() + flag * cnt;
flag = flag & (lower[dgt+1]== lower[dgt]+ 1) ? 1 : 0;
}
return dp;
}
}
classSolution:
defsolve(self, A: list[int], B: int, C: int) -> int:
S = str(C)
d, n = len(A), len(S)
if d ==0or B > n:
return0if B < n:
if A[0] ==0and B >1:
return (d-1) * (d ** (B-1))
return d ** B
digits = [int(x) for x in S]
lower = [0]*11for x in A:
lower[x+1] =1for i in range(1, 11):
lower[i] += lower[i-1]
dp, flag =0, 1for i in range(B):
dgt = digits[i]
cnt = lower[dgt]
if i ==0and A[0] ==0and B >1:
cnt -=1 dp = dp * d + flag * cnt
flag = flag and (lower[dgt+1] == lower[dgt] +1)
return dp