题目描述

难度分:$2197$

输入长度$\leq 2 \times 10^5$的字符串$s$和整数$k(1 \leq k \leq 16)$。

$s$表示一个十六进制数，无前导零。

在$[1,s]$中，有多少个（无前导零的）十六进制数，恰好包含$k$个不同的数字？这里的数字指$0$~$9$和A~F。

答案模$10^9+7$。

输入样例$1$

10 1

输出样例$1$

15

输入样例$2$

FF 2

输出样例$2$

225

输入样例$3$

100 2

输出样例$3$

226

输入样例$4$

1A8FD02 4

输出样例$4$

3784674

输入样例$5$

DEADBEEFDEADBEEEEEEEEF 16

输出样例$5$

153954073

算法

数位DP

按照数位DP的套路来做，从高位往低位填数。

状态定义

$f[i][mask][islimit][isnum]$表示填到$i$这个数位，之前所填数位的数字组成了$mask$这个二进制状态，前面数字贴合上界情况为$islimit$（如果前面填的数贴合上界$s$的数位则有$islimit=1$），当前是不是一个数字都没填$isnum$（填了数就满足$isnum=1$）。这里如果直接让第二维是二进制数$mask$肯定是会爆空间的，我们可以只存$mask$中$1$的数目，这样就让第二维的大小从$2^k$变为$k$。

状态转移

对于边界情况，当所有数位都填完时，只要$isnum=1$并且$mask$中$1$的数量是$k$，则产生了一个合法的数字。

对于一般情况，尝试当前位填的数字$d \in [0,ub]$，如果$islimit=1$，那么$ub=s[i]$，否则$ub=15$。

1. 如果$isnum=0$，那么就还是一个数都没填，状态转移方程为$f[i][popcount(mask)][islimit][isnum]=f[i+1][popcount(mask)][0][isnum]$。
2. 如果填了数字$d$，那么二进制状态$mask$就会变为$mask \lor 2^d$，状态转移方程为$f[i][popcount(mask)][islimit][isnum]=\Sigma_{d=1-isnum}^{ub}f[i+1][popcount(mask \lor 2^d)][islimit \land d=ub][1]$。

其中$popcount(num)$，表示$num$在二进制下有多少个$1$。

复杂度分析

时间复杂度

状态数量为$O(nk)$。单次转移需要遍历$d \in [0,ub]$，可以看成是$O(k)$。所以整个算法的时间复杂度为$O(nk^2)$。

空间复杂度

空间消耗的瓶颈就是状态数组，额外空间复杂度为状态数量$O(nk)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int MOD = 1e9 + 7, N = 200010;
string s;
int k, n, f[N][16][2][2];

int dfs(int i, int mask, int islimit, int isnum) {
    if(i == n) {
        return f[i][__builtin_popcount(mask)][islimit][isnum] = (isnum && __builtin_popcount(mask) == k)? 1: 0;
    }
    int &v = f[i][__builtin_popcount(mask)][islimit][isnum];
    if(v != -1) return v;
    int cnt = !isnum? dfs(i + 1, mask, 0, 0): 0;
    int digit = isdigit(s[i])? s[i] - '0': s[i] - 'A' + 10;
    int ub = islimit? digit: 15;
    for(int d = 1 - isnum; d <= ub; d++) {
        cnt = (cnt + dfs(i + 1, mask|(1<<d), islimit && d == ub, 1)) % MOD;
    }
    return v = cnt;
}

int main() {
    cin >> s >> k;
    n = s.size();
    memset(f, -1, sizeof f);
    cout << dfs(0, 0, 1, 0) << endl;
    return 0;
}