Question

P2602 数字计数

求 \([a,b]\) 中的所有整数中，每个数出现的次数

Solution

数位DP板子题

定义 \(dp[i]\) 表示 \(i\) 位数的每种数字有多少个，我们把 \(0\) 和 \(00\) 看成两种不同的数，并且 \(00\) 中算 \(0\) 出现过两次

显然，\(0\sim 9\) 在 \(i\) 位数中出现的次数是一样的，得出递推式

数字 \(x\) 在最高位上的次数为 \(10^{i-1}\) ，在其他位上的次数位 \(dp[i-1]\times 10\)

考虑前缀和，把 \([a,b]\) 拆成 \([0,a-1]\) 和 \([0,b]\)，问题转化成求 \([0,x]\) 的各个数出现的次数了

假设当前最高位的数字为 \(num[i]\)

不考虑最高位，每个数字都出现了 \(num[i]\times dp[i-1]\) 次

for(int j=0;j<=9;j++)
    cnt[j] += dp[i-1]*num[i];

最高位的数字： \([0,num[i])\) 出现了 \(10^{i-1}\) 次，\(num[i]\) 出现的次数就是后面的数 \(+1\)，例如 \(324\) 中，最高位 \(3\) 出现的次数就是 \(25\)

for(int j=0;j<num[i];j++)
    cnt[j] += ten[i-1];
    LL num2 = 0;
for(int j=i-1;j;j--)
    num2 = num2*10+num[j];
cnt[num[i]] += num2 + 1;

最后排除前导零的影响

cnt[0] -= ten[i-1];

还有一种是记忆化 DFS 的写法，定义都有所不同，定义 \(dp[pos][sum]\) 表示枚举到第 \(pos\) 位，前面有 \(sum\) 个 \(now\)

此时需要特判前导零 \(lead\) ，和前面是否被卡死 \(limit\)

如果前面没有被卡死且没有前导零的情况下，可以使用记忆化

当然，也可以把 \(lead\) 和 \(limit\) 定义到记忆化里面去

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
LL ten[maxn],dp[maxn];
LL cnta[maxn],cntb[maxn];
int num[maxn];

void init(){
    ten[0]=1;
    for(int i=1;i<maxn;i++){
        dp[i] = i*ten[i-1];
        ten[i] = ten[i-1]*10;;
    }
}

void solve(LL x,LL *cnt){
    int len = 0;
    while(x){
        num[++len] = x%10;
        x/=10;
    }
    for(int i=len;i;i--){
        for(int j=0;j<=9;j++)
            cnt[j] += dp[i-1]*num[i];
        for(int j=0;j<num[i];j++)
            cnt[j] += ten[i-1];
        LL num2 = 0;
        for(int j=i-1;j;j--)
            num2 = num2*10+num[j];
        cnt[num[i]] += num2 + 1;
        cnt[0] -= ten[i-1];
    }
}

int main(){
    init();
    LL a,b; cin>>a>>b;
    solve(a-1,cnta),solve(b,cntb);
    for(int i=0;i<=9;i++)
        cout<<cntb[i]-cnta[i]<<" ";
    return 0;
}

记忆化 DFS

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
LL num[maxn],now,dp[maxn][maxn];

LL dfs(int pos,int sum,bool lead,bool limit){
    LL ans = 0;
    if(pos == 0) return sum;
    if( !lead && !limit && dp[pos][sum]!=-1 ) return dp[pos][sum]; //记忆化搜索
    int up = limit ? num[pos] : 9; //这一位的最大值
    for(int i=0;i<=up;i++){
        if( i==0 && lead )
            ans += dfs(pos-1, sum, true, limit && i==up); //计算 000-099
        else if(i==now)
            ans += dfs(pos-1, sum+1, false, limit && i==up); //计算 x00-x99
        else if(i!=now)
            ans += dfs(pos-1, sum, false, limit && i==up); //计算其他
    }
    if(!lead && !limit) dp[pos][sum] = ans; //可以重复使用部分
    return ans;
}

LL solve(LL x){
    int len = 0;
    while(x){
        num[++len] = x%10;
        x/=10;
    }
    memset(dp,-1,sizeof dp);
    return dfs(len,0,true,true);
}

int main(){
    LL a,b; cin>>a>>b;
    for(int i=0;i<10;i++){
        now = i;
        cout<<solve(b)-solve(a-1)<<" ";
    }
    return 0;
}