FZU 2113 Jason的特殊爱好

题意：

　　　给定区间[a,b]，求将区间中所有数写在黑板上，要写的数字‘1’的次数。(1 <= a,b <= 10^8)

解法：

　　　将题转化成f(b+1) - f(a)的形式。普通的数位DP。

tag:数位DP

 /*

  * Author:  Plumrain

  * Created Time:  2013-12-15 23:53

  * fILE nAME: dp-fzU-2113.cpp

  */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 typedef long long int64;

 int64 d[][];

 int dit[];

 int64 mypow(int64 p, int64 n)

 {

     int64 ret = ;

     while (n){

         if (n & ) ret *= p;

         n >>= ;

         p *= p;

     }

     return ret;

 }

 void d_init()

 {

     CLR (d);

     d[][] = ;

     for (int i = ; i < ; ++ i){

         d[i][] = mypow(, i-);

         for (int j = ; j < ; ++ j)

             for (int k = ; k < ; ++ k)

                 d[i][j] += d[i-][k];

     }

 }

 int64 gao(int64 x)

 {

     int len = ;

     while (x){

         dit[len++] = x % ;

         x /= ;

     }

     dit[len] = ;

     int64 ret = ;

     int flag = ;

     for (int i = len-; i >= ; -- i){

         ret += dit[i] * mypow(, i) * flag;

         for (int j = ; j < dit[i]; ++ j)

             ret += d[i+][j];

         if (dit[i] == ) ++ flag;

     }

     return ret;

 }

 int main()

 {

     d_init();

     int64 a, b;

     while (cin >> a >> b)

         cout << gao(b+) - gao(a) << endl;

     return ;

 }