【BZOJ-1833】count数字计数数位DP

2023-08-03 20:26:40

1833: [ZJOI2010]count 数字计数

Time Limit: 3 Sec Memory Limit: 64 MB
Submit:
2494 Solved: 1101
[Submit][Status][Discuss]

Description

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

Input

输入文件中仅包含一行两个整数a、b，含义如上所述。

Output

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20
20

HINT

30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

Source

Day1

Solution

裸的数位DP，但其实并不是特别的水

首先F[i][j][k]表示位数为i的最高位为j的k种数的个数

按照十进制拆分，预处理后统计答案

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

long long L,R;

long long F[][][],ans1[],ans2[];

void prework()

{

    for (int i=; i<=; i++) F[][i][i]=;

    long long tmp=;

    for (int i=; i<=; i++)

        {

            tmp*=;

            F[i][][]=F[i-][][]*+F[i-][][]+tmp;

            for (int j=; j<=; j++)

                F[i][][j]=F[i-][][j]*+F[i-][j][j];

            for (int j=; j<=; j++)

                {

                    F[i][j][]=F[i-][][]*+F[i-][][];

                    for (int k=; k<=; k++)

                        if (j==k)

                            F[i][j][k]=F[i-][][k]*+F[i-][k][k]+tmp;

                        else

                            F[i][j][k]=F[i-][][k]*+F[i-][k][k];

                }

        }

}

long long cf(int x)

{

    long long re=;

    for (int i=; i<x; i++)

        re*=;

    return re;

}

void Calc(long long x,long long *ans)

{

    int digit[]={},len=; long long y=x;

    while (x) {digit[++len]=x%; x/=;}

    for (int i=; i<len; i++)

        for (int j=; j<=; j++)

            for (int k=; k<=; k++)

                ans[k]+=F[i][j][k];

    for (int i=len; i>=; i--)

        {

            for (int j=; j<=digit[i]-; j++)

                {

                    if (i==len && j==) continue;

                    for (int k=; k<=; k++) ans[k]+=F[i][j][k];

                }

            ans[digit[i]]+=y%cf(i)+;

        }

}

int main()

{

    prework();

    scanf("%lld%lld",&L,&R);

    Calc(L-,ans1); Calc(R,ans2);

    printf("%lld",ans2[]-ans1[]);

    for (int i=; i<=; i++) printf(" %lld",ans2[i]-ans1[i]);

    return ;

}

自己一开始YY的出错了..

码农公寓