Skip to main content

数位 DP

参考资料​

例题​

P2602 [ZJOI2010] 数字计数​

洛谷 P2602 [ZJOI2010] 数字计数

给定两个正整数 aa 和 bb，求在 [a,b][a,b] 中的所有整数中，每个数码(digit)各出现了多少次。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=15;
ll t1[N],t2[N];
ll ans1[N],ans2[N];
void init()
{
    t2[0]=1;
    for(int i=1;i<N;i++)
    {
        t1[i]=t1[i-1]*10+t2[i-1];
        t2[i]=t2[i-1]*10;
    }
}
void solve(ll x,ll *ans)
{
    ll t[N];
    int cnt=0;
    while(x)
    {
        t[++cnt]=x%10;
        x/=10;
    } 
    for(int i=cnt;i>=1;i--)
    {
        for(int j=0;j<=9;j++)
        {
        	ans[j]+=t1[i-1]*t[i];
        }
        for(int j=0;j<t[i];j++)
        {
        	ans[j]+=t2[i-1];
        }
        ll k=0;
        for(int j=i-1;j>=1;j--)
        {
            k=k*10+t[j];
        }
        ans[t[i]]+=k+1;
        ans[0]-=t2[i-1];
    } 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	init();
	ll a,b;
    cin>>a>>b;
    solve(a-1,ans1);
    solve(b,ans2);
    for(int i=0;i<=9;i++)
    {
    	cout<<ans2[i]-ans1[i]<<' ';
    }
    return 0;
}