牛客寒假算法基础集训营3 G. 处女座和小姐姐（三）(数位dp)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[20];
ll dp[20][20];

ll dfs(int pos, int pre, bool limit){
  if(pos == -1) return 1;
  if(!limit && dp[pos][pre] != -1) return dp[pos][pre];
  int up = limit ? a[pos] : 9;
  ll ans = 0;
  for(int i=0;i<=up;i++){
    if(i == 6)continue;
    ans += dfs(pos - 1, i, limit && i == a[pos]);
  }
  return limit ? ans : dp[pos][pre] = ans;
}

ll solve(ll x){
  int pos = 0;
  while(x){
    a[pos++] = x % 10;
    x /= 10;
  }
  return dfs(pos - 1, 0, true);
}

int main()
{
  ll l, r;
  scanf("%lld%lld",&l, &r);
  memset(dp,-1,sizeof(dp));
  ll xx = r - l + 1;
  ll yy = solve(r) - solve(l - 1);
  printf("%lld\n",xx - yy);
  return 0;
}