DP

背包

数位

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

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

  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;
      }
  }