Challenge: Digit Products
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 60.0 / 60
Submission status: Accepted
Submission score: 1.0
Submission ID: 464756451
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/digit-products/problem
Cerinta
Let $D(X)$ be a function that calculates the digit product of $X$ in base $10$ without leading zeros. For instance:
$D(0) = 0$
$D(234) = 2 \times 3 \times 4 = 24$
$D(104) = 1 \times 0 \times 4 = 0$
You are given three positive integers $A, B$ and $K$. Determine how many integers exist in the range $[A, B]$ whose digit product equals $K$. Formally speaking, you are required to count the number of distinct integer solutions of $X$ where $A \leqslant X \leqslant B$ and $D(X) = K$.Input Format
The first line contains $T$, the number of test cases. <br>
The next $T$ lines each contain three positive integers: $A$, $B$ and $K$, respectively.
**Constraints**
$T \leqslant 10000$
$1 \leqslant A \leqslant B \leqslant 10^{100}$
$1 \leqslant K \leqslant 10^{18}$Output Format
For each test case, print the following line:
*Case* $X$$: Y$
$X$ is the test case number, starting at $1$.
$Y$ is the number of integers in the interval $[A, B]$ whose digit product is equal to $K$.
Because $Y$ can be a huge number, print it modulo $(10^9 + 7)$.Cod sursa
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
static const int MAXLEN = 100;
struct State {
uint8_t a, b, c, d;
};
static inline uint32_t packExp(int a, int b, int c, int d) {
return (uint32_t)a | ((uint32_t)b << 6) | ((uint32_t)c << 12) | ((uint32_t)d << 18);
}
string decOne(string s) {
if (s == "0") return "0";
int i = (int)s.size() - 1;
while (i >= 0 && s[i] == '0') {
s[i] = '9';
--i;
}
if (i >= 0) s[i]--;
int p = 0;
while (p + 1 < (int)s.size() && s[p] == '0') ++p;
s.erase(0, p);
if (s.empty()) return "0";
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 1) Build all exponent states (a,b,c,d) with 2^a 3^b 5^c 7^d <= 1e18.
const unsigned long long LIM = 1000000000000000000ULL;
vector<State> states;
states.reserve(70000);
unordered_map<uint32_t, int> id;
id.reserve(140000);
for (int a = 0;; ++a) {
__int128 v2 = 1;
for (int i = 0; i < a; ++i) {
v2 *= 2;
if (v2 > LIM) break;
}
if (v2 > LIM) break;
for (int b = 0;; ++b) {
__int128 v23 = v2;
for (int i = 0; i < b; ++i) {
v23 *= 3;
if (v23 > LIM) break;
}
if (v23 > LIM) break;
for (int c = 0;; ++c) {
__int128 v235 = v23;
for (int i = 0; i < c; ++i) {
v235 *= 5;
if (v235 > LIM) break;
}
if (v235 > LIM) break;
__int128 cur = v235;
for (int d = 0;; ++d) {
if (cur > LIM) break;
uint32_t key = packExp(a, b, c, d);
int idx = (int)states.size();
states.push_back(State{(uint8_t)a, (uint8_t)b, (uint8_t)c, (uint8_t)d});
id[key] = idx;
cur *= 7;
}
}
}
}
int S = (int)states.size();
int idOne = id[packExp(0, 0, 0, 0)];
// 2) Precompute backward transitions by placing one digit in {1..9}.
int da[10] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0};
int db[10] = {0, 0, 0, 1, 0, 0, 1, 0, 0, 2};
int dc[10] = {0, 0, 0, 0, 0, 1, 0, 0, 0, 0};
int dd[10] = {0, 0, 0, 0, 0, 0, 0, 1, 0, 0};
vector<array<int, 10>> prevState(S);
for (int i = 0; i < S; ++i) {
for (int d = 1; d <= 9; ++d) prevState[i][d] = -1;
auto st = states[i];
for (int d = 1; d <= 9; ++d) {
if (st.a < da[d] || st.b < db[d] || st.c < dc[d] || st.d < dd[d]) continue;
uint32_t key = packExp(st.a - da[d], st.b - db[d], st.c - dc[d], st.d - dd[d]);
auto it = id.find(key);
if (it != id.end()) prevState[i][d] = it->second;
}
}
// 3) DP[len][state] = number of len-digit strings over {1..9} with product exponents=state.
vector<vector<int>> dp(MAXLEN + 1, vector<int>(S, 0));
dp[0][idOne] = 1;
for (int len = 1; len <= MAXLEN; ++len) {
auto &cur = dp[len];
auto &prv = dp[len - 1];
for (int s = 0; s < S; ++s) {
long long ways = 0;
for (int dig = 1; dig <= 9; ++dig) {
int ps = prevState[s][dig];
if (ps >= 0) {
ways += prv[ps];
if (ways >= (long long)MOD * MOD) ways %= MOD;
}
}
cur[s] = (int)(ways % MOD);
}
}
auto countLE = [&](const string &X, int targetState) -> int {
if (X == "0") return 0;
int n = (int)X.size();
long long ans = 0;
// Shorter lengths.
for (int len = 1; len < n; ++len) {
ans += dp[len][targetState];
if (ans >= MOD) ans -= MOD;
}
// Same length with prefix restriction.
int remState = targetState;
bool alive = true;
for (int i = 0; i < n && alive; ++i) {
int lim = X[i] - '0';
int from = (i == 0 ? 1 : 0);
for (int dig = from; dig < lim; ++dig) {
if (dig == 0) continue; // product would be 0, impossible for K>=1
int ps = prevState[remState][dig];
if (ps >= 0) {
ans += dp[n - i - 1][ps];
ans %= MOD;
}
}
if (lim == 0) {
alive = false;
break;
}
int ns = prevState[remState][lim];
if (ns < 0) {
alive = false;
break;
}
remState = ns;
}
if (alive && remState == idOne) {
ans++;
if (ans >= MOD) ans -= MOD;
}
return (int)ans;
};
auto factorState = [&](unsigned long long K) -> int {
int a = 0, b = 0, c = 0, d = 0;
while (K % 2ULL == 0ULL) { K /= 2ULL; ++a; }
while (K % 3ULL == 0ULL) { K /= 3ULL; ++b; }
while (K % 5ULL == 0ULL) { K /= 5ULL; ++c; }
while (K % 7ULL == 0ULL) { K /= 7ULL; ++d; }
if (K != 1ULL) return -1;
uint32_t key = packExp(a, b, c, d);
auto it = id.find(key);
if (it == id.end()) return -1;
return it->second;
};
int T;
cin >> T;
for (int tc = 1; tc <= T; ++tc) {
string A, B;
unsigned long long K;
cin >> A >> B >> K;
int st = factorState(K);
int ans = 0;
if (st != -1) {
int right = countLE(B, st);
string A1 = decOne(A);
int left = countLE(A1, st);
ans = right - left;
if (ans < 0) ans += MOD;
}
cout << "Case " << tc << ": " << ans << '\n';
}
return 0;
}
HackerRank Combinatorics – Digit Products