[HDU2089]不要62 题解

/**
 * @Author: Mingyu Li
 * @Date:   2019-03-14T13:44:58+08:00
 * @Email:  class11limingyu@126.com
 * @Filename: HDU2089.cpp
 * @Last modified by:   Mingyu Li
 * @Last modified time: 2019-03-14T14:02:19+08:00
 */

#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)
typedef long long LL;
template < typename T > void sc(T& t) {
  char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < typename T , typename... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}

LL dp[20][11] , d[20];

// dp(i,j) : 还差i位 上一位是x，接下来不同的数的个数

LL f(LL i , LL j) {
  if(dp[i][j] != -1) return dp[i][j];
  if(!i) return dp[i][j] = 1;
  else {
    LL ans = 0;
    Go(digit , 0 , 9) if(digit != 4 && !(j == 6 && digit == 2)) ans += f(i-1 , digit);
    return dp[i][j] = ans;
  }
}

LL calc(LL x) {
  int m = 0;
  while(x) {
    d[m++] = x%10; x/=10;
  }
  LL ans = 0;
  Go(i , 1 , m-1) {
    Go(j , 1 , 9) if(j != 4) ans += f(i-1 , j);
  }
//  std::cerr <<"%% " << ans << std::endl;
  int last = 0;
  God(i , m-1 , 0) {
    Go(j , (i == m-1) ? 1 : 0 , d[i]-1) if(j != 4 && !(last == 6 && j == 2)) ans += f(i , j);
    if(d[i] == 4) break;
    if(last == 6 && d[i] == 2) break;
    last = d[i];
  }
  return ans;
}
int main() {
  memset(dp , -1 , sizeof(dp));
  LL l , r;
  while(1) {
    sc(l , r);
    if(!l && !r) return 0;
    //std::cout << calc(l) << std::endl;
    std::cout << calc(r+1) - calc(l) << std::endl;
  }
  return 0;
}