个人向口胡题解（4/3）

ABC295 F

题意：十进制下，给定两个正整数\(L、 R\)和一个字符串\(S\)，设\(F(x)\)为\(S\)在\(x\)中一共出现多少次，求\(\sum_{x=L}^{R}F(x)\)。

如\(S=22, F(122)=1,F(123)=0,F(222)=2\)

思路：可以按\(S\)在\(x\)中匹配的位置分别计算贡献，匹配的位置知道了，那么合法的数个数就是这位的贡献。下界的限制有点麻烦，一个很常用的trick：\(\sum_{x=L}^{R}F(x)=\sum_{x=1}^{R}F(x)-\sum_{x=1}^{L-1}F(x)\)，这样合法的数就是所有小于等于上界的数，这些数的个数可以二分出来。如果\(S\)是以\(0\)开头需要特判。

\(code\):

LL get_num(LL i, int k) {
    int t = k - len_s + 1;
    if (t < 0) return 1e17;
    i--;
    if (s[0] == '0') i += p10[t];
    LL p = i / p10[t], q = i % p10[t];
    return p * p10[k + 1] + stoll(s) * p10[t] + q;
}

LL calc(LL x) {
    len_s = s.length();
    LL res = 0;
    rep (k, 0, 15) {  // 从低位到高位枚举s[0]的起始位置k
        LL mn = get_num(1, k);
        if (mn > x) continue;
        LL l = 1, r = p10[16 - len_s];
        while (l < r) {
          LL mid = l + r + 1 >> 1;
          if (get_num(mid, k) <= x) l = mid;
          else r = mid - 1;
        }
        res += l;
    }
    return res;
}

void work() {
    LL L, R;
    cin >> s >> L >> R;
    cout << calc(R) - calc(L - 1) << '\n';
}