首页 > 代码库 > [bzoj1833][ZJOI2010][count] (数位dp)

[bzoj1833][ZJOI2010][count] (数位dp)

2024-08-31 21:16:54   217人阅读

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。

Solution

十进制数位dp

设f(i,j,k)表示第i位以j开头的数含有多少个数字k

先预处理出f[i][j][k]数组

转移的时候从高到低转移

#include<stdio.h>#define LL unsigned long longint len,zt[33];LL f[33][33][33],bt[33],a,b,ans[33];void init() {    bt[1]=1;    for(int i=2; i<=13; i++)        bt[i]=bt[i-1]*10;    for(int i=0; i<10; i++)        f[1][i][i]=1;    for(int i=2; i<=13; i++)        for(int j=0; j<10; j++)            for(int k=0; k<10; k++) {                for(int l=0; l<10; l++)                    f[i][j][l]+=f[i-1][k][l];                f[i][k][k]+=bt[i-1]; } }void solve(LL x,LL d) {    LL bef=x;    for(len=0; x; x/=10)        zt[++len]=x%10;    for(int i=1; i<len; i++)        for(int j=1; j<10; j++)            for(int k=0; k<10; k++)                ans[k]+=d*f[i][j][k];    for(int i=len; i; i--) {        for(int j=0; j<zt[i]; j++) {            if(!j && i==len)continue;            for(int k=0; k<10; k++)                ans[k]+=d*f[i][j][k]; }        ans[zt[i]]+=d*(bef%bt[i]+1); } }int main() {    init();    scanf("%lld%lld",&a,&b);    solve(b,1);    solve(a-1,-1);    for(int i=0; i<9; i++)        printf("%lld ",ans[i]);        printf("%lld\n",ans[9]);    return 0; }

 

[bzoj1833][ZJOI2010][count] (数位dp)


联系
我们