给定一个长度不超过 $17$ 的字符串及整数 $K$，字符串由 $0~9$ 组成，且无前导 $0$。求使用其中的数字排列成无前导 $0$ 且能被 $17$ 整除的第 $K$ 小的数。$K\le 17!$。

比如，输入为 2242223 2，输出为 2242232。

使用状态压缩 DP，f[n][val][state] 表示从个位（个位为第 $1$ 位）填到第 $n$ 位时，还没有用过的数字对应的状态编号为 State，还没有用过的数字构成的数对 $17$ 取模的结果为 val，且整体为 $17$ 倍数的情况下的合法方案数。(现在的 $n$ 位数加上 $\text{val}\times 10^n$ 之后是 $17$ 的倍数）。

01 #include <iostream>
02 using namespace std;
03
04 typedef long long ll;
05 const int N=20，M=20005;
06 int cnt[N]; char s[N];
07 ll f[N][N][M]，d[N]，K;
08
09 inline ll dfs(int k, int val, int sta) {
10     ①;
11     if (~f[k][val][sta]) return f[k][val][sta];
12     ll res = 0;
13     for (int i = 0; i <= 9; ++i) {
14         int lim = sta / d[i] % (cnt[i] + 1);
15         if (lim == cnt[i]) continue;
16         res += ②;
17     }
18     return f[k][val][sta] = res;
19 }
20
21 int main(){
22     ③;
23     scanf("%s", s+1); cin >> K;
24     int len = strlen(s + 1);
25     for (int i = 1; i <= len; ++i) 
26         ++cnt[s[i] - '0'];
27     d[0] = 1;
28     for (int i = 1; i <= 9; ++i)
29         d[i]= ④;
30     int sta = 0, val = 0; ll now = 0;
31     for (int i = len; i >= 1; --i)
32         for (int j = i==len?1:0; j <= 9; ++j) {
33             int lim = ⑤;
34             if (lim == cnt[j]) continue;
35             ll tmp = dfs(i - 1, (val * 10 + j) % 17, sta + d[j]);
36             if (now + tmp >= K) {
37                 putchar(j + '0');
38                 val = (val * 10 + j)% 17;
39                 sta += d[j];
40                 break;
41             }
42             now += tmp;
43         }
44     cout << endl;
45     return 0;
46 }

1. ① 处应填 {{ select(1) }}

• if (k) return !val;
• if (!k) return !val;
• if (!k) return val;
• if (k) return val;

2. ② 处应填 {{ select(2) }}

• dfs(k + 1, (val - i * 10) % 17, sta + d[i])
• dfs(k - 1, (val * 10 + i) % 17, sta - d[i])
• dfs(k + 1, (val - i * 10) % 17, sta - d[i])
• dfs(k - 1, (val * 10 + i) % 17, sta + d[i])

3. ③ 处应填 {{ select(3) }}

• memset(f, 255, sizeof(f))
• memset(f, 0, sizeof(f))
• memset(f, 127, sizeof(f))
• memset(f, 128, sizeof(f))

4. ④ 处应填 {{ select(4) }}

• d[i-1] * (cnt[i - 1])
• d[i-1] * (cnt[i])
• d[i-1] * (cnt[i - 1] + 1)
• d[i-1] * (cnt[i] + 1)

5. ⑤ 处应填 {{ select(5) }}

• sta / d[j] % (cnt[j] + 1)
• sta / d[j - 1] % (cnt[j])
• sta / d[j - 1] % (cnt[j] + 1)
• sta / d[j] % (cnt[j])