(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$的位数):

需要注意的是由于没有前导零, $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
#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;
}