Divisibilidade das cartas

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using i64 = long long;

const int MAX = 13;

string lo, hi;

int timer;
int dp[MAX][2][2][10];
int calc[MAX][2][2][10];

int solve(int i, int canLo, int canHi, int rem) {
  if (i == lo.size()) return rem;

  if (calc[i][canLo][canHi][rem] == timer) return dp[i][canLo][canHi][rem];

  int ans = 0;

  int l = canLo ? 0 : lo[i] - '0';
  int r = canHi ? 9 : hi[i] - '0';
  for (int k = l; k <= r; ++k) {
    ans = (ans + solve(i + 1, canLo | (k != l), canHi | (k != r), rem + k >= 9 ? rem + k - 9 : rem + k)) % 9;
  }

  calc[i][canLo][canHi][rem] = timer;
  return dp[i][canLo][canHi][rem] = ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  i64 l, r; cin >> l >> r;

  lo = to_string(l);
  hi = to_string(r);

  while (lo.size() < hi.size()) lo = '0' + lo;
  while (hi.size() < lo.size()) hi = '0' + hi;

  ++timer;
  cout << solve(0, 0, 0, 0) << '\n';
}