(luogu2602) 数字计数 (ZJOI2010)

发表于 分类于 ， ，

原题链接

思路:

首先，由前缀和的思想，区间 \([a,b]\) 的计数可以化为两个计数: \([0,b]\) 和 \([0,a-1]\) 的计数， 相减即可得到原来区间计数的答案.

对 \([0,x]\) 内数位上数字的计数则可使用数位 dp 解决.

设 \(d_1(i,j,k)\) 为当第 i 位数字为 j 时数字 k 的数量， \(d_2(i,j)\) 为第 i 位为 \(x_i\) 且小于 \(\overline{x_ix_{i-1} \cdots x_1}\)(即 x 的前 i 位组成的数) 时数字 \(j\) 的数量.

\(d_1\) 的计算较为简单，有:

较为复杂的是 \(d_2\) 的计算，有:

答案 \(ans_k\) 为 (\(c\) 为 \(x\) 的位数):

\[ \begin{aligned} ans_k = & \sum_{i=1}^{c-1}\sum_{j=1}^{9}d_1(i,j,k) \\ + & \sum_{j=1}^{x_c-1}d_1(c,j,k) \\ + & d_2(c,k) \end{aligned} \]

需要注意的是由于没有前导零，\(d_1(i,0,k)\) 只在计算 \(d_1\) 时使用.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <cstring>
typedef long long LL;

LL dp1[20][10][10],dp2[20][10]; //即d_1, d_2
LL ans[10],anss[10];    //[0,a-1],[0,b]的答案

void fdp(LL x) {    //计算函数
    memset(ans,0,sizeof ans);
    memset(dp1,0,sizeof dp1);
    memset(dp2,0,sizeof dp2);   //初始化
    if(x<10) {  //直接输出
        for(int i(0);i<=9;++i) {
            if(i>x) {
                break;
            }
            ans[i] = 1;
        }
        return;
    }
    int dc(0);  //x的位数
    int dig[20];    //x每位的数
    while(x) {  //计算dig
        dig[++dc] = x%10;
        x /= 10;
    }
    for(int i(0);i<=9;++i) {    //初始化
        dp1[1][i][i] = 1;
        ans[i] = 1;
    }
    dp2[1][dig[1]] = 1;
    LL pt(1),ptt(dig[1]);   //10^i, x的前i-1位
    for(int i(2);i<=dc;++i) {
        pt *= 10;
        for(int j(0);j<=9;++j) {
            if(j==dig[i]) { //当j=dig[i]时更新d_2
                for(int k(0);k<dig[i-1];++k) {
                    for(int ii(0);ii<=9;++ii) {
                        dp2[i][ii] += dp1[i-1][k][ii];
                    }
                }
                for(int k(0);k<=9;++k) {
                    dp2[i][k] += dp2[i-1][k];
                }
                dp2[i][dig[i]] += ptt+1;
            }
            for(int k(0);k<=9;++k) {    //更新d_1
                for(int ii(0);ii<=9;++ii) {
                    dp1[i][j][k] += dp1[i-1][ii][k];
                }
            }
            dp1[i][j][j] += pt;
        }
        if(i!=dc) {
            for(int j(1);j<=9;++j) {
                for(int k(0);k<=9;++k) {
                    ans[k] += dp1[i][j][k];
                }
            }
        } else {
            for(int j(1);j<dig[i];++j) {
                for(int k(0);k<=9;++k) {
                    ans[k] += dp1[i][j][k];
                }
            }
            for(int j(0);j<=9;++j) {
                ans[j] += dp2[i][j];
            }
        }
        ptt += dig[i]*pt;
    }
}

int main() {
    LL a,b;
    scanf("%lld %lld",&a,&b);

    fdp(b);
    memcpy(anss,ans,sizeof anss);
    fdp(a-1);
    for(int i(0);i<=9;++i) {
        anss[i] -= ans[i];  //相减得到最终结果
        printf("%lld ",anss[i]);
    }
    return 0;
}