SP3928 MDIGITS - Counting Digits 题解

题意：

给定两个整数 \(a\) 和 \(b\)，求 \(a\) 和 \(b\) 之间的所有数字中 \(0\) ~ \(9\) 出现次数。

例如，\(a\) = \(1024\)，\(b\) = \(1032\)，则 \(a\) 和 \(b\) 之间共有 \(9\) 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 \(10\) 次，1 出现 \(10\) 次，2 出现 \(7\) 次，3 出现 \(3\) 次等等……

数位dp的基础题

设 \(f_i\) 表示满 \(i\) 位数字（包括前导零），每种数字的出现次数 \[ f_1 = 1 \\f_i = f_{i-1} \times 10 + 10^{i-1} \] 其中 \(f_{i-1}\times 10\) 是 \(i-1\) 位及以下位的贡献

例如 \(\tt{7000\sim7999,~8000\sim8999}\)

显然 \(\tt{000\sim999}\)出现了 \(10\) 次

而 \(10^{i-1}\) 是第 \(i\) 位的贡献，比如 \(\tt{9000 \sim 9999}\) ，第 \(4\) 位的 \(\tt{9}\) 出现了 \(10^3\) 次

然后我们再考虑怎么获得答案

首先 \([l,r]\) 可以拆分为 \([0,l-1],~[0,r]\) 两个询问（基本的容斥）

然后考虑一个数 \(\tt{\overline{ABC}}\) ，不难发现，\(\tt{0}\) 到 \(\tt{\overline{A00}}\) 每个非最高位数都出现了 \(\tt{A}\) \(\times f_2\) 次

而最高位 \(\tt{0\sim A-1}\) 都各出现了 \(10^2\) 次

注：这里 \(\tt 0\) 是前导零，所以其实不会算进去，这里只是为了方便分析

那么 \(\tt{A}\) 呢？不难发现它出现了 \(\tt{\overline{BC}+1}\) 次

对于 \(\tt{B}\) ，同样的处理方式。

~~怎么一股机翻的味道~~

然后我们就搞定这道题了

时间复杂度 \(O(Qlb)\)

其中 \(l\) 表示最大位数， \(b\) 表示进制，这题里为 \(10\)

代码：（非dfs写法）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int a,b,mi[25],cnt1[25],cnt2[25],num[25],f[25];
void clear()
{
    memset(cnt1,0,sizeof(cnt1));
    memset(cnt2,0,sizeof(cnt2));
}
void solve(int x,int *cnt)
{
    int len=0;
    memset(num,0,sizeof(num));
    while(x)
    {
        num[++len]=x%10;
        x/=10;
    }
    for(int i=len; i>=1; i--)
    {
        for(int j=0; j<=9; j++)
            cnt[j]+=f[i-1]*num[i];
        for(int j=0; j<num[i]; j++)
            cnt[j]+=mi[i-1];
        int res=0;
        for(int j=i-1; j>=1; j--)
        {
            res = res * 10 + num[j];
        }
        cnt[num[i]]+=res+1;
        cnt[0]-=mi[i-1];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    mi[0]=1;
    for(int i=1; i<=18; i++)
    {
        f[i]=f[i-1]*10+mi[i-1];
        mi[i]=10*mi[i-1];
    }
    while(cin >> a >> b)
    {
        if(!a&&!b)return 0;
        if(a>b)swap(a,b);
        clear();
        solve(a-1,cnt1);solve(b,cnt2);
        for(int i=0; i<=9; i++)
            cout << cnt2[i]-cnt1[i] << " \n"[i==9];
    }
    return 0;
}