题解 | #数位小孩#

/********************
Author:  Nanfeng1997
Contest: NowCoder
URL:     https://ac.nowcoder.com/acm/problem/233129
When:    2022-03-15 14:21:34

Memory:  524288MB
Time:    2000ms
********************/
#include  <bits/stdc++.h>
using namespace std;
using LL = long long;

LL dp[11][11][2][2][2];
int a[11], cnt;
bool vis[20];

LL dfs(int pos, int last, bool limit, bool lead, bool flag) {
  if(pos == cnt) return flag;
  LL &ans = dp[pos][last][limit][lead][flag];
  if(ans != -1) return ans;  ans = 0;
  for(int i = 0; i <= (limit ? a[pos] : 9); i ++ ) {
    if(lead) {
      ans += dfs(pos + 1, i, limit && i == a[pos], lead && !i, flag || i == 1);
    } else if(vis[last + i]) {
      ans += dfs(pos + 1, i, limit && i == a[pos], lead && !i, flag || i == 1);
    }
  }
  return ans;
}

LL f(LL x) {
  if(!x) return x; 
  cnt = 0;
  memset(a, 0, sizeof a);
  memset(dp, -1, sizeof dp);
  while(x) a[cnt ++ ] = x % 10, x /= 10;
  reverse(a, a + cnt);
  return dfs(0, 0, true, true, false);
}

void solve() {
  vis[2] = 1, vis[3] = 1, vis[5] = 1, vis[7] = 1;
  vis[11] = 1, vis[13] = 1, vis[17] = 1;
  LL l, r; cin >> l >> r;
  cout << f(r) - f(l - 1) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1; //cin >> T;
  while(T --) solve();

  return 0;
}