Vol4

ZJOI2010 count
BZOJ1833

定义$f(i,j,k)$，代表长为i，开头为j，digit k能出现多少次 。

这可以轻易地被DP出来。

接下来，我们要求$[1,n]$的digit出现数量。

很明显，可以将位数不足n的数全部用$f(i,j,k)$预处理出来，接下来的可以视为前缀唯一。可以容易地递推出来。

#include <cstdio>
#include <cstdlib> 
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
typedef long long ll;
using namespace std;
struct Data{
    ll ans[10];
    Data(){
        memset(ans,0,sizeof(ans)); 
    } 
};
Data operator +(const Data& a,const Data& b)
{
    Data t;
    for(int i=0;i<=9;i++)
        t.ans[i]=a.ans[i]+b.ans[i];
    return t;
}
ll l,r;
ll ten[20];
Data f[20][15]; //f[i][j].ans[k]：长为i，开头为j，digit k能出现多少次 
void GetPerDigit(ll u,int* dig)
{
    dig[0]=0;
    while(u>0){
        dig[++dig[0]]=u%10;
        u/=10;
    }   
}
Data Calc(ll u)
{
    int dig[20];
    Data ans;
    if(u==0)
        return ans;
    GetPerDigit(u,dig); 
    for(int i=1;i<dig[0];i++)
        for(int j=1;j<=9;j++)
            ans=ans+f[i][j];
    for(int i=1;i<dig[dig[0]];i++)
        ans=ans+f[dig[0]][i];
    ans.ans[dig[dig[0]]]+=(u%ten[dig[0]-1])+1; 
    for(int i=dig[0]-1;i>=1;i--){
        for(int j=0;j<dig[i];j++)
            ans=ans+f[i][j];
        ans.ans[dig[i]]+=(u%ten[i-1])+1;
    }
    return ans;
}
void Solve()
{
    Data ans1=Calc(l-1),ans2=Calc(r);
    for(int i=0;i<=8;i++)
        cout<<ans2.ans[i]-ans1.ans[i]<<" ";
    cout<<ans2.ans[9]-ans1.ans[9];
}
void First()
{
    ten[0]=1;
    for(int i=1;i<=12;i++)
        ten[i]=ten[i-1]*10;
    for(int i=0;i<=9;i++)
        f[1][i].ans[i]=1;
    for(int i=2;i<=12;i++)
        for(int j=0;j<=9;j++){
            f[i][j].ans[j]=ten[i-1];
            for(int k=0;k<=9;k++)
                f[i][j]=f[i][j]+f[i-1][k];
        }
}
void ReadData()
{
    cin>>l>>r;
}
void Close()
{
    fclose(stdin);  
} 
int main()
{
    ReadData();
    First();
    Solve();
    Close();
    return 0;
}