Hello Leetcode, I would like to share a very interesting DP problem I found in Atcoder ABC Round 194. It is so brilliant that I would like to take you to have a look in this difficult but interesting DP problem.

If you are a Chinese reader, or you can read Chinese, you may see my blog about this problem here:
https://tom0727.gitee.io/post/023-at-abc194f/

Problem Statement

Link: https://atcoder.jp/contests/abc194/tasks/abc194_f
Official Tutorial: https://atcoder.jp/contests/abc194/editorial/859

Given an Integer 1 <= N <= 16^(2e5), find the number of integers between 1 and N, that have exactly K distinct digits in the hexadecimal notation without leading zeros.
Print the count modulo (10^9+7).

Solution

To solve this problem we can use DP. We would like to count the number of Integers x that satisfy the conditions.
You may notice that it is very troublesome to handle the case when x might be greater than N.

To deal with this problem, let's start DP with the most significant digit.

Let dp[i][j] be: We are processing the first i most significant digits, and we are using j distinct digits, and also satisfy the following conditions:

1. x is strictly less than the first i most significant digits of N.
2. x != 0.

The value of dp[i][j] is the number of x that satisfy the above conditions.

Now, consider the state transition. Because of condition 1, no matter which digit we choose for the current digit, we will still satisfy condition 1.
So we have our first equation: (we have 16 digits in total to choose from)

for (ll j = 2; j <= k; j++) {
    dp[i][j] = (dp[i][j] + dp[i-1][j-1] * (16-j+1)) % mod;
    dp[i][j] = (dp[i][j] + dp[i-1][j] * j) % mod;
}

Now we might notice that, we only consider the case where the first i-1 digits have at least one legal digits (that is, not all of them are zeros). So if the first i-1 digits are all zeros, no matter which digit we choose for the current digit, we will still satisfy condition 1.
So we have our second equation: (Notice we can't choose 0 for this digit, because of condition 2).

dp[i][1] = (dp[i-1][1] + 15) % mod;

Finally, note that we haven't handled the case where the first i-1 digits of x and N are exactly the same. We can easily handle this case independently, just notice that for the current ith digit of x, we cannot choose a digit that is greater or equal than the ith digit of N (Because of the condition 1).
The equation will be given in the codes.

At last, we need to take care N itself. Because N is not included in the dp array, we just check whether N satisfy the conditions.

Code

using namespace std;
#include <bits/stdc++.h>

#define ll long long

const int mod = 1e9+7;
const int maxn = 2e5+5;

ll dp[maxn][18];
string s;
int k;

map<char, int> dict;
set<int> used;

int main() {

    for (int i = 0; i <= 9; i++) dict[(char)(i+'0')] = i;
    int o = 10;
    for (char c = 'A'; c <= 'F'; c++) dict[c] = o++;

    cin >> s >> k;
    int n = s.size();
    dp[1][1] = dict[s[0]] - 1;
    used.insert(dict[s[0]]);

    for (ll i = 2; i <= n; i++) {
        char c = s[i-1];
        dp[i][1] = (dp[i-1][1] + 15) % mod;  //equation 1
        int cur = dict[c];

        for (ll j = 2; j <= k; j++) {
            dp[i][j] = (dp[i][j] + dp[i-1][j-1] * (16-j+1)) % mod;     // equation 2
            dp[i][j] = (dp[i][j] + dp[i-1][j] * j) % mod;   // equation 2
        }

        int pre = used.size();  // The number of distinct digits in N[0...(i-1)]
        for (int j = 0; j < cur; j++) {
            if (!used.count(j)) {   
                dp[i][pre+1]++;   // equation 3
            } else dp[i][pre]++;   // equation 3
        }

        used.insert(cur);
    }
    if (used.size() == k) dp[n][k]++;
    ll ans = dp[n][k] % mod;
    cout << ans << endl;
}