写此题的过程:$TLE->5000ms->2500ms->1500ms$。
显然有效的数只有$10^{18}$范围内只含因子$2、3、5、7$的数,$dfs$枚举出有效数之后离散化存储,有效数共有约$66000$个,为了效率采用了手写哈希表,并预处理出每个有效数除以$1-9$的商用来加速转移,也可以视作自动机。
本题要求的是数字和,记录每个状态的数字数量,在这个状态后面新加一位$i$的时候,位权$\times$个数$\times i$即为增量。
对于$k$为零和非零,分开处理,$k=0$时非常好处理,不加赘述。
$k$非零时,为了不用每次重新初始化数组,我们反其道而行之,每次用$k$去除以当前枚举的数,记录$k$还剩余多少,当$k$不能被$i$整除时,无法转移,直接截断搜索,最后$k$恰好剩余$1$则统计贡献。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using i64 = long long;
const int N = 21, M = 67000, H = 130007;
const i64 lim = 1e18;
const int mod = 20120427;
const int a[] = {2, 3, 5, 7};
int nums[N], len;
int cnt;
int p10[N];
int to[M][10];
i64 l, r, k;
int target;
struct State {
int s0, s1;
State(int t = 1) {
s0 = t, s1 = 0;
}
State operator+= (const State &b) {
(s0 += b.s0) %= mod;
(s1 += b.s1) %= mod;
return *this;
}
State operator+= (const int &k) {
(s1 += 1ll * k * s0 % mod) %= mod;
return *this;
}
} f[N][M], f0[N][2][2];
struct Hash_Table {
int h[H], ne[M], id[M], idx;
i64 e[M];
void init() {
idx = 0, memset(h, -1, sizeof h);
}
void push(i64 v) {
int x = v % H;
for (int i = h[x]; ~i; i = ne[i])
if (e[i] == v)
return;
e[idx] = v, id[idx] = ++cnt;
ne[idx] = h[x], h[x] = idx++;
}
int find(i64 v) {
int x = v % H;
for (int i = h[x]; ~i; i = ne[i])
if (e[i] == v)
return id[i];
return 0;
}
} h;
void dfs(int u, i64 prod) {
if (u == 4) return h.push(prod);
for (int i = 0; ; i++) {
dfs(u + 1, prod);
if (prod * a[u] > lim) break;
prod *= a[u];
}
}
void init() {
p10[0] = 1;
for (int i = 1; i <= 18; i++) p10[i] = (p10[i - 1] * 10) % mod;
h.init();
dfs(0, 1);
for (int i = 0; i < h.idx; i++) {
i64 v = h.e[i], id = h.id[i];
for (int j = 1; j < 10; j++) {
if (v % j) to[id][j] = -1;
else to[id][j] = h.find(v / j);
}
}
}
State dfs(int pos, int id, int lim, int lead) {
if (!pos) return id == 1;
State& st = f[pos][id];
if (!lim && !lead && ~st.s0) return st;
int upper = lim ? nums[pos] : 9;
State res = 0;
if (lead) res += dfs(pos - 1, id, 0, 1);
for (int i = 1; i <= upper; i++)
if (~to[id][i])
res += dfs(pos - 1, to[id][i], lim & i == upper, 0) += 1ll * i * p10[pos - 1] % mod;
if (!lim && !lead) st = res;
return res;
}
State dfs0(int pos, int zero, int lim, int lead) {
if (!pos) return zero;
State& st = f0[pos][zero][lead];
if (!lim && ~st.s0) return st;
int upper = lim ? nums[pos] : 9;
State res = 0;
for (int i = 0; i <= upper; i++) {
if (lead & !i) res += dfs0(pos - 1, 0, lim & i == upper, 1);
else res += dfs0(pos - 1, zero | !i, lim & i == upper, 0) += 1ll * i * p10[pos - 1] % mod;
}
if (!lim) st = res;
return res;
}
int dp(i64 x) {
if (!target) return 0;
len = 0;
while (x) nums[++len] = x % 10, x /= 10;
return dfs(len, target, 1, 1).s1;
}
int dp0(i64 x) {
len = 0;
while (x) nums[++len] = x % 10, x /= 10;
return dfs0(len, 0, 1, 1).s1;
}
signed main() {
init();
int T;
cin >> T;
memset(f, -1, sizeof f);
memset(f0, -1, sizeof f0);
while (T--) {
cin >> l >> r >> k;
target = h.find(k);
if (!k) cout << ((dp0(r) - dp0(l - 1)) % mod + mod) % mod << '\n';
else cout << ((dp(r) - dp(l - 1)) % mod + mod) % mod << '\n';
}
return 0;
}