LG2602/BZOJ1833 「ZJOI2010」数字计数 数位DP

问题描述

LG2602

BZOJ1833

题解

数位\(\mathrm{DP}\)板子题。

注意限制位数、前导零。

\([a,b]=[1,b]-[1,a-1]\)

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int a,b;
int len;
int opt[21][3][21][3];
int lim[21];
void count(int x){
    len=0;
    while(x){
        lim[++len]=x%10,x/=10;
    }
}

int dp(int siz,bool lit,int base,bool pre,int pos){
    int re=0;
    if(!siz) return base;
    if(opt[siz][lit][base][pre]!=-1) return opt[siz][lit][base][pre];
    for(int i=0;i<=9;i++){
        if(!lit&&i>lim[siz]) break;
        re=re+dp(siz-1,lit||(i<lim[siz]),base+((!pre||i)&&(i==pos)),pre&&(!i),pos);
    }
    return opt[siz][lit][base][pre]=re;
}

int solve(int x,int pos){
    count(x);
    memset(opt,-1,sizeof(opt));
    return dp(len,0,0,1,pos);
}

signed main(){
    read(a);read(b);
    for(int i=0;i<=9;i++){
        printf("%lld ",solve(b,i)-solve(a-1,i));
    }
    return 0;
}