デジタルDP入門BZOJ 1833問題解(復習が必要)

明らかに、このブログはPoPoQQQの影响を受けて、コードは自分で一回たたいて、基本的にPoPoQQQのコードと同じで、ここで题解を书きます
タイトル:http://www.lydsy.com/JudgeOnline/problem.php?id=1833
1833: [ZJOI2010]count
数値カウント
Time Limit: 3 Sec Memory Limit: 64 MB Submit: 3421 Solved: 1510
Description
2つの正の整数aとbを与え,[a,b]のすべての整数の中で,各デジタル(digit)がそれぞれ何回出現したかを求める.
Input
入力ファイルには、上述したように、1行2つの整数a,bのみが含まれます.
Output
出力ファイルには1行10個の整数が含まれており、0-9が[a,b]に何回現れたかを示す.
Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT
30%のデータのうち、a<=b<=10^6;100%のデータのうち、a<=b<=10^12である.
コメントコード:

#include
#include
#include
#include
#define dnt long long
using namespace std;
dnt cnt[10],f[100];

void Resolve(dnt x,dnt pos){
    //        ，          while         ,     12345(         ),      now/pos  x    ,           x%10     
    x=10 pos=1000
    while(x){
        cnt[x%10]+=pos;
        x/=10;
    }
} 
void Digital_DP(dnt x,int ff){
    int i,j;
    dnt pos,now;
    //     pos         
    for(i=1,pos=10;pos<x;i++,pos*=10){
        for(j=0;j<=9;j++){
            cnt[j]+=f[i-1]*9*ff;
            //      ,i-1              ,     0,  *9(             )
        }
        for(j=1;j<=9;j++){
            cnt[j]+=pos/10*ff;
            //        j   ,              10,  j=1 ,123456  1       100000,   pos/10(          ，        )
        } 
    }
    now=pos/=10;i--;//   now        
    //   pos   x     ,       
    while(now<x){
        while(now+pos<=x){
            dnt temp=now/pos;
            //temp (        /       ),         ,         
            Resolve(temp,pos*ff);
            for(j=0;j<=9;j++){
                cnt[j]+=f[i]*ff;
            }
            now+=pos;//             now  
        }
        pos/=10;i--;
    }
} 
int main(){
    dnt a,b,pos;
    int i;
    f[1]=1;
    for(i=2,pos=10;i<=12;i++,pos*=10){
        f[i]=f[i-1]*10+pos; 
    }
    //               0 i       ,    ,            0           ,    ,         ,            ,     ,             ,           0 ,    01,03,09       
    cin>>a>>b;
    Digital_DP(b+1,1);//      b+1,                  ,     1 b   
    Digital_DP(a,-1);//      1,-1 ff ,             1 b    1 a-1   
    for(i=0;i<=9;i++)  
    printf("%lld%c",cnt[i],i==9?'
':' ');
    //        , PE   
    return 0;
}