数字计数

难度：5星

解法1

我们设 $dp[i][j][k]dp[i][j][k]$ 为长度为 $ii$ ，首位是 $jj$ 的数字中 $kk$ 出现的次数。

推导递推关系时我们枚举长度为 $ii$ 的数字中首位和次首位的数字，即可得递推关系 $dp[i][j][p]=dp[i-1][k][p]dp[i][j][p]\; =\; dp[i-1][k][p]$ 其中 $ii$ 是数字长度， $jj$ 是第 $ii$ 位数字的首位， $kk$ 是第 $i-1i-1$ 位数字。即长度为 $ii$ 的所有数字一定包含了长度是 $i-1i-1$ 的数中出现的所有数字。

并且，当第 $ii$ 位数字是 $jj$ 时，前 $i-1i-1$ 位选任意数字皆出现 $jj$ ，因此 $dp[i][j][j]=dp[i][j][j]+10^{i-1}dp[i][j][j]\; =\; dp[i][j][j]\; +\; 10^\{i-1\}$ 。

我们设 $ans[i][0]ans[i][0]$ 是数字 $ii$ 在 $[0,l][0,l]$ 中出现的次数 , $ans[i][1]ans[i][1]$ 是数字 $ii$ 在 $[0,r][0,r]$ 中出现的次数。

为了优化常数，我们预处理出可能用到的所有的 $10^{i-1}10^\{i-1\}$ 并命名为 $prepre$ 数组

要求 $[l,r][l,r]$ 之间每个数字出现的次数，用 $[0,r+1)[0,r+1)$ 减去 $[0,l)[0,l)$ 每个数字出现的次数即可。

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

const int N = 13;
// dp[i][j][k]  代表长度为i，以j位首位的数中k出现的次数
// pre[i] 10的i-1次方
// ans[i][0/1] [0,l/r]中i出现的次数
ll l , r , dp[N+10][10][10] , pre[N+10] , nums[N+10] , ans[N+10][2];

void solve(ll x,int idx) {
    ll tmp = x;
    int cnt = 0;
    while (tmp) {
        nums[++cnt] = tmp%10;
        tmp/=10;
    }
    //位数小于cnt的一定可以全部使用
    for (int i = 1 ; i < cnt ; i ++) {
        for (int j = 1 ; j <= 9 ; j ++) {
            for (int k = 0 ; k <= 9 ; k ++) {
                ans[k][idx] += dp[i][j][k];
            }
        }
    }
    //位数等于cnt并且首位小于x最高位的一定可以全部使用
    for (int j = 1 ; j < nums[cnt] ; j ++) {
        for (int k = 0 ; k <= 9 ; k ++) {
            ans[k][idx] += dp[cnt][j][k];
        }
    }
    //枚举至第i位，此时设[i+1,n]位一定与x相同
    for (int i = cnt - 1 ; i >= 1 ; i --) {
        //同上枚举首位小于第i位的一定可以使用
        for (int j = 0 ; j < nums[i] ; j ++) {
            for (int k = 0 ; k <= 9 ; k ++) {
                ans[k][idx] += dp[i][j][k];
            }
        }
        //保证[i+1,num]相同，这些相同数字也应该计入答案
        for (int p = cnt ; p > i ; p --) ans[nums[p]][idx] += nums[i]*pre[i];
    }
}

int main() {
    scanf("%lld%lld",&l,&r);
    // preprocess
    for (int i = 0 ; i <= 9 ; i ++) dp[1][i][i] = 1;
    pre[1] = 1;
    for (int i = 2 ; i <= N ; i ++) pre[i] = pre[i-1]*10 ;
    for(int i = 2 ; i <= N ; i ++) {
        for(int j = 0 ; j <= 9 ; j ++) { 
            for(int k = 0 ; k <= 9 ; k ++) {

                for(int p = 0 ; p <= 9 ; p ++) dp[i][j][p]+=dp[i-1][k][p];
            
            }
            dp[i][j][j] += pre[i];
        }
    }
    memset(ans,0,sizeof ans);
    solve(l,0);
    solve(r+1,1);
    for (int i = 0 ; i <= 9 ; i ++) {
        printf("%lld ",ans[i][1]-ans[i][0]);
    }
}