SRM526 Div2 Hard

1000
メモ化する。
memo[桁数][4の数][7の数][まだ一致しているか]

const int L = 11;

lli memo[L][L][L][2];
string s;

lli rec(int len, int _4, int _7, bool small)
{
  if (len == s.size()) return abs(_4 - _7);
  if (memo[len][_4][_7][small] != -1) return memo[len][_4][_7][small];

  lli sum = 0;
 
  int begin, end;
  if (small) {
    begin = 0, end = 9;
  } else {
    begin = 0, end = s[len] - '0';
  }

  for (int i = begin; i <= end; ++i) {
    sum += rec(len + 1, _4 + (i == 4), _7 + (i == 7), small || i < s[len] - '0');
  }

  return memo[len][_4][_7][small] = sum;
}

class SumOfLuckiness {
public:
  long long theSum(int A, int B)
  {   
    char buff[L];

    fill(&memo[0][0][0][0], &memo[L - 1][L - 1][L - 1][2], -1);
    sprintf(buff, "%d", A - 1);
    s = string(buff);
    lli a = rec(0, 0, 0, false);

    fill(&memo[0][0][0][0], &memo[L - 1][L - 1][L - 1][2], -1);
    sprintf(buff, "%d", B);
    s = string(buff);
    lli b = rec(0, 0, 0, false);

    return b - a;
  }
};