统计次数

给定两个正整数 \(n\) 和 \(k\)，请你求出从 \(1 \sim n\) 这 \(n\) 个正整数的十进制表示中 \(k\) 出现的次数。

数据范围

\(1 \leq\) n \(\leq 10 ^ 6\)

\(1 \leq\) k \(\leq 9\)

输入样例

12 1

输出样例

找规律

\(0 \sim 9\) 中出现 k 的次数必定是 \(1\)；
\(0 \sim 99\) 中出现 k 的次数必定是 \(10 + 1 * 10\)
\(0 \sim 999\) 中出现 k 的次数必定是 \(100 + (10 + 1 * 10) * 10\)

若假设函数 f(n) 可以求出 \(0 \sim 999···9\) n 个 \(9\) 中出现 k 的次数，那么可以得到递推公式：

f(n) = pow(10, n - 1) + f(n - 1) * 10

求出 0 到 n 个 9 中出现 k 的次数

LL f(LL k)
{
    if (k <= 1) return k;
    LL res = pow(10, k - 1);
    return res + f(k - 1) * 10;
}

定义函数 fk(n, k) 可以求出 n 的十进制表示中出现 k 的次数，参考代码为：

LL fk(LL n, LL k)
{
    LL res = 0;
    while (n)
    {
        if (n % 10 == k) res ++;
        n /= 10;
    }
    return res;
}

那么如果知道了 n 是 a 位十进制数，并且最高位为 c，那么可以确定 0 ~ c * pow(10, a - 1) - 1 范围内 k 出现的次数为：

res += f(a - 1) * c

接下来我们只需要从 c * pow(10, a - 1) 一直遍历到 n 一个数一个数的求出 k 出现的次数并累加即可，这样时间复杂度估测降至 \(O(\frac{n}{c})\)，\(c\) 为 \(n\) 的最高位数字。

代码参考

#include <iostream>
#include <cmath>

using namespace std;
typedef long long LL;
const int N = int (1e6 + 10);

LL n, m;
LL res;

LL f(LL k)
{
    if (k <= 1) return k;
    LL res = pow(10, k - 1);
    return res + f(k - 1) * 10;
}

LL fk(LL n, LL k)
{
    LL res = 0;
    while (n)
    {
        if (n % 10 == k) res ++;
        n /= 10;
    }
    return res;
}

int main(void)
{
    scanf ("%lld%lld", &n, &m);
    LL a = 0, b = n, c, d;
    while (b) a ++, b /= 10;
    c = n / (LL) (pow(10, a - 1));
    res += f(a - 1) * c;
    if (c > m) res += pow(10, a - 1);
    d = c * pow(10, a - 1);
    while (d <= n)
    {
        res += fk(d ++, m);
    }
    cout << res << endl;

    return 0;
}

进一步优化

代码参考

#include <iostream>
#include <cmath>

using namespace std;
typedef long long LL;
const int N = int (1e6 + 10);

LL n, m, res;

LL f(int k)
{
    if (k <= 1) return k == 1 ? 1 : 0;
    return pow(10, k - 1) + f(k - 1) * 10;
}

LL fa(int n)
{
    LL res = 0;
    while (n) res ++, n /= 10;
    return res;
}

LL fk(int n, int k)
{
    LL res = 0;
    while (n) res += (n % 10 == k ? 1 : 0), n /= 10;
    return res;
}

LL fs(LL n, LL k)
{
    if (n == 0) return 0;
    LL a = fa(n), c, res;
    c = n / (LL)(pow(10, a - 1));
    res = f(a - 1) * c;
    if (k < c) res += (LL)(pow(10, a - 1));
    else if (k == c)
        res += n % (LL)(pow(10, a - 1)) + 1;
    return res + fs(n % (LL)(pow(10, a - 1)), k);
}

int main(void)
{
    scanf ("%lld%lld", &n, &m);
    printf ("%lld\n", fs(n, m));
    return 0;
}

时间复杂度估测为 \(O(log_{10}(n))\)

代码理解样例: n = 91011, k = 1

先求出 \(0 \sim 9999\) 中必定会出现 1 的次数为 f(4)；
对于万位来说，从 \(0 \sim 9999, 10000 \sim 19999, 20000 \sim 29999, \cdots, 80000 \sim 89999\) 总共必定有 \(9 * f(4)\) 个 \(k\) 出现的次数，接下来只需要求 \(90000 \sim 91011\) 中 \(k\) 出现的次数即可；
在 \(90000 \sim 91011\) 中，如果最高位是 \(k\) 那么 \(k\) 出现的次数就是 \(1011 + 1\) 个；如果最高位大于 \(k\)，那么 \(k\) 出现的次数需要加上 \(10000\) 个，因为上面第 2 步并没有统计最高位是 \(k\) 的次数，现在补上；如果 \(k\) 大于最高位，就加 0.
按照相同逻辑计算除去最高位的 \(n = 1011\)，不断递归下去直到 \(n = 0\)。

探究暴力代码的时间复杂度

暴力代码

#include <iostream>

using namespace std;
typedef long long LL;
const int N = int (1e6 + 10);

LL n, m, res;

LL fk(LL n, LL k)
{
    LL res = 0;
    while (n)
    {
        if (n % 10 == k) res ++;
        n /= 10;
    }
    return res;
}

int main(void)
{
    cin >> n >> m;
    for (LL i = 1; i <= n; i ++) res += fk(i, m);
    cout << res << endl;
}

时间复杂度估测为 \(O(a \times n)\)，\(c\) 为 \(n\) 的最高位，\(a\) 为 \(n\) 的位数。

递推

如果知道了 1011 中 1 出现的次数，那么 10111 中 1 出现的次数就是 1011 中 1 的次数加上 10111 末尾是否是 1.

递推逻辑是从位数少的推到出位数多的，递推公式为：

f[n] = f[n / 10] + (n % 10 == 1 ? 1 : 0)

时间复杂度是 \(O(n)\)

代码参考

#include <iostream>

using namespace std;
typedef long long LL;
const int N = int (2e6 + 10);

LL n, m, res;
LL a[N];

int main(void)
{
    scanf ("%lld%lld", &n, &m);
    for (LL i = 0; i <= n; i ++)
    {
        if (i % 10 == m) a[i] ++; a[i] += a[i / 10];
        res += a[i];
    }
    printf ("%lld\n", res);
}