算法
(数位 dp)
令 $g(x) = \sum\limits_{k=0}^x f(k)$,则有 $\sum\limits_{k=L}^R f(k) = g(R) - g(L-1)$
$ g(x) = \sum\limits_{k=0}^x\sum\limits_{i} [\text{从} ~k ~\text{的第} ~i ~\text{个字符开始包含} ~S] = \sum\limits_i \text{在} ~x ~\text{以内从第} ~i ~\text{个字符开始包含} ~S ~\text{的整数个数} $
然后跑数位dp即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
ll g(string s, ll x) {
int n = s.size();
vector<int> a;
while (x) {
a.push_back(x%10);
x /= 10;
}
reverse(a.begin(), a.end());
int m = a.size();
ll res = 0;
rep(si, m-n+1) {
vector dp(2, vector<ll>(2));
dp[0][0] = 1;
rep(i, m) {
vector p(2, vector<ll>(2));
swap(dp, p);
rep(j, 2)rep(k, 2)rep(d, 10) {
if (si <= i and i < si+n) {
if (s[i-si]-'0' != d) continue;
if (k == 0 and d == 0) continue; // leading zero
}
int nj = j, nk = k;
if (j == 0) {
if (d < a[i]) nj = 1;
if (d > a[i]) continue;
}
if (d) nk = 1;
dp[nj][nk] += p[j][k];
}
}
res += dp[0][1]+dp[1][1];
}
return res;
}
void solve() {
string s;
ll l, r;
cin >> s >> l >> r;
ll ans = g(s, r) - g(s, l-1);
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}