BZOJ 1833 数字计数 ( 桁DP )

Problem 1833. -- [ZJOI2010]count 数字计数
Given a ≤ 1e12, b ≤ 1e12, find frequency for each digit in range [ a , b ].
dp[ i ][ j ][ k ]: chose i digits, less flag, not zero
Note that when transferring, we are to add the number of ways of its prefix.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXAB = 1e12 + 12;
const int MAXP = 15;
#define rep( i, a ) for(int i = 0; i < ( int )( a ); ++i)

string a, b;

struct Data{
    ll cnt[ 10 ];
    ll way;
    Data(){}
    void init(){
        way = 0;
        memset( cnt, 0, sizeof(cnt) );
    }
    void print(){
        rep( i, 10 ) printf("%lld\n", cnt[ i ]);
    }
};

Data dp[ MAXP ][ 2 ][ 2 ];

Data count(const string &s, bool inc){
    rep( i, s.size() + 1 ) rep( j, 2 ) rep( k, 2 )
        dp[ i ][ j ][ k ].init();
    dp[ 0 ][ 0 ][ 0 ].way = 1;
    rep( i, s.size() ) rep( j, 2 ) rep( k, 2 ){
        if( dp[ i ][ j ][ k ].way == 0 ) continue;
        int lim = j ? 9 : s[ i ] - '0';
        rep( d, lim + 1 ){
            rep( z, 10 ){
                dp[ i + 1 ][ j || d < lim ][ k || d > 0 ].cnt[ z ]
                += dp[ i ][ j ][ k ].cnt[ z ];
            }
            if( k || d > 0 ){
                dp[ i + 1 ][ j || d < lim ][ k || d > 0 ].cnt[ d ]
                += dp[ i ][ j ][ k ].way;
            }
            dp[ i + 1 ][ j || d < lim ][ k || d > 0 ].way
            += dp[ i ][ j ][ k ].way;
        }
    }
    Data res; res.init();
    rep( j, 2 ){
        if( !j && !inc ) continue;
        rep( z, 10 )
            res.cnt[ z ] += dp[ s.size() ][ j ][ 1 ].cnt[ z ];
    }
    return res;
}

void solve(){
    Data x = count( a, false );
    Data y = count( b, true );
    for(int i = 0; i < 10; ++i)
        printf("%lld%c", y.cnt[ i ] - x.cnt[ i ], i == 9 ? '\n' : ' ');
}

int main(){
    cin >> a >> b;
    solve();
    return 0;
}