ABC 194 F.Digits Paradise in Hexadecimal

#include <bits/stdc++.h>
#define DEBUG if(0)
typedef long long ll;
using namespace std;

const int maxSz = 2e5, maxCnt = 16;
const ll mod = 1e9 + 7;
ll dp[maxSz][maxCnt + 1][2][2];

char s[maxSz + 1];
int a[maxSz];
int sz, k;

ll solve(int state, int pos, bool lmt, bool lead) {
    int cnt = __builtin_popcount(state);
    if (cnt > k) return 0;
    if (pos == sz) return cnt == k && lead;

    ll &ans = dp[pos][cnt][lmt][lead];
    if (ans != -1) return ans;

    ans = 0;
    int llmt = (lmt ? a[pos] : 15);
    for (int i = 0; i <= llmt; i++)
        ans = (ans + solve((!i && !lead) ? state : state | (1 << i), pos + 1, lmt & (i == llmt), lead | i)) % mod;
    return ans;
}

int main() {
    cin >> s >> k;
    sz = strlen(s);
    for (int i = 0; i < sz; i++) {
        a[i] = s[i] - (isdigit(s[i]) ? ‘0‘ : ‘A‘ - 10);
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0, 1, 0) << endl;

  return 0;
}