preface
网上目前还没看到我的方法，就大概讲一下做法
solution
首先想到贪心，考虑 \([l, r]\) 的最大次数，一定是找到最小的 \(x\) 满足 \(l \sim x\) 的位数的和大于等于 \(k\)，然后递归的求解 \([x + 1, r]\)，易证。
还是考虑将 \(Query (l, r)\) 拆分成 \(Query (1, r)\) 和 \(Query (1, l - 1)\)
那么我们就有一个简单的数位 \(dp\)，\(dfs (step, tot, last, limit)\) 表示从最高位考虑到 \(step\) 位，这些位的位数和位 \(tot\)，上一个区间剩下 \(last\) 的位数和，是或否顶到上届，容易写出。
但是我们发现 \(Query (1, r) - Query (1, l - 1) \neq Query (l, r)\)，问题在于 \([1, l - 1]\) 这个区间剩下的位数和给到 \([l, r]\) 可能会让答案多一。
怎么处理这个问题呢？考虑暴力就是如果当前考虑到了 \(l\)，那么他就不从上一个区间继承 \(last\) 了，考虑记忆化搜索优化，那么只需要判断当前这个状态是否包含 \(l\)，再加一维状态 \(past\) 用以判断当前这个区间是否包含 \(l\)。
code
//我看着，天真的我自己
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define MP(x,y) make_pair (x, y)
#define PII pair <int, int>
#define db double
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
void read (T &x) {
x = 0; bool fl_for_x = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') fl_for_x = 0;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar ();
}
if (!fl_for_x) x = -x;
}
template <typename T, typename... Args>
void read (T &x, Args&... args) {
read (x), read (args...);
}
const int Maxn_For_Print = 30;
int Tp_For_Print, St_For_Print[Maxn_For_Print + 5];
template <typename T>
void write (T x) {
if (x == 0) {
putchar ('0');
return;
}
if (x < 0) {
x = -x;
putchar ('-');
}
while (x) {
St_For_Print[++Tp_For_Print] = x % 10;
x /= 10;
}
while (Tp_For_Print) {
putchar (St_For_Print[Tp_For_Print--] + '0');
}
}
template <typename T>
void print (T x, char ch) {
write (x), putchar (ch);
}
const int Maxn = 18;
const int Maxtot = 9 * 17;
const int Maxlast = 1e3;
LL l, r, k, w[Maxn + 5];
int tp, x[Maxn + 5];
pair <LL, int> dp[2][Maxn + 5][Maxtot + 5][Maxlast + 5];
bool vis[2][Maxn + 5][Maxtot + 5][Maxlast + 5];
LL calc (LL past, int step) {
if (past <= l && l <= past + w[step] - 1) return 1;
else return 0;
}
pair <LL, int> dfs (int step, int tot, int last, int Limit, LL past) {
if (!Limit && vis[calc (past, step)][step][tot][last]) return dp[calc (past, step)][step][tot][last];
if (step == 0) {
if (past == l) {
if (tot >= k) return MP (1, 0);
else return MP (0, tot);
}
last += tot;
if (last >= k) return MP (1, 0);
else return MP (0, last);
}
int Up = Limit ? x[step] : 9;
pair <LL, int> res = MP (0, last);
rep (i, 0, Up) {
pair <LL, int> tmp = dfs (step - 1, tot + i, res.se, Limit & (i == Up), past + (w[step - 1] * i));
res = MP (res.fi + tmp.fi, tmp.se);
}
if (!Limit) dp[calc (past, step)][step][tot][last] = res, vis[calc (past, step)][step][tot][last] = 1;
return res;
}
LL Query (LL qwq) {
tp = 0;
while (qwq) {
x[++tp] = qwq % 10;
qwq /= 10;
}
return dfs (tp, 0, 0, 1, 0).fi;
}
signed main () {
// freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.in", "r", stdin);
// freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.out", "w", stdout);
// freopen ("transport.in", "r", stdin);
// freopen ("transport.out", "w", stdout);
w[0] = 1; rep (i, 1, Maxn) w[i] = w[i - 1] * 10;
read (l, r, k);
write (Query (r) - Query (l - 1));
return 0;
}