DP

DP

背包

数位

  • $1-n$ 所有数中,数位 $0-9$ 的数量

    $f[i]$ 表示前 $i$ 位出现的数码次数

    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
    ll f[20],cnt[10];
    void fun(ll n){
    mem0(cnt);
    if(!n)return;
    if(!f[1]){
    f[1]=1;
    ll s=10;
    for(int i=2;i<20;i++)f[i]=f[i-1]*10+s,s*=10;
    }
    ll k=n,m;
    int w=0,i,j,sum[15];
    while(k) sum[++w]=k%10,k/=10;
    for (m=1,i=1; i<w; i++){
    cnt[0]+=f[i-1]*9;
    for (j=1; j<=9; j++) cnt[j]+=f[i-1]*9+m;
    m*=10;
    }
    k=n-sum[w]*m;
    for (i=1; i<sum[w]; i++) cnt[i]+=m;
    for (i=0; i<=9; i++) cnt[i]+=f[w-1]*(sum[w]-1);
    cnt[sum[w]]+=k+1;
    for (i=w-1; i; i--){
    m/=10,k-=sum[i]*m;
    for (j=0; j<sum[i]; j++) cnt[j]+=m;
    for (j=0; j<=9; j++) cnt[j]+=f[i-1]*sum[i];
    cnt[sum[i]]+=k+1;
    }
    }