题解：CF747F Igor and Interesting Numbers

· · 题解

下面为了方便叙述把题目中的 k 换成了 n。数据很小我们可以使用十分暴力的方法做。我们注意到应先求出数字有多少位，我们从低到高枚举，假设我们枚举到有 len 位，设 dp_{i, j} 表示前 i 个数字填了 j 个，我们用 [1, 16] 来表示 16 进制下的 [0, f]，由于 0 不能于最前面，显然有初始状态 dp_{1, i} = \binom{len - 1}{i}。对于转移，不难发现枚举 i 填了 k 个有：

dp_{i, j} = \sum_{k \le \min(j, t)} \binom{len - (j - k)}{k} dp_{i - 1, j - k}

那么 i 位答案就为 dp_{16, len}，方便表示我们设其为 f，那么若 f \ge n 说明 len 就是正确的；否则将 n 减去 f 继续枚举 len + 1。枚举完位数我们从高到低枚举每一位的数，注意第 len 位应从 2 开始枚举而其他位可以从 1 开始，因为显然最高位不能为 0。设 lim_x 表示 x 还可以用多少次，假设我们第 i 位枚举到了 j，那么我们设第 i 位枚举到了 j 的方案数为 f，如果 f \ge n 说明第 i 位就是 j，将 lim_j 减 1 然后枚举下一位即可；否则我们将 n 减去 f 继续枚举 j + 1。现在考虑怎么求 f，我们可以类似的 dp，设 dp_{i, j} 表示前 i 个数填了 j 个的方案数，显然有 f = dp_{16, len}，其中 len 表示枚举到的位数，由于没有最高位不为 0 的限制显然有初始状态 dp_{0, 0} = 1，显然有类似的转移：

dp_{i, j} = \sum_{k \le \min(j, lim_i)} \binom{len - (j - k)}{k} dp_{i - 1, j - k}

做完了。

code