第K小数

GitHub跳转原题关系图返回列表

把「剩余数字多重集」当状态预处理余数分布,再按位试填,用可被 17 整除的后缀方案数逼近第 K 小数。

OJ: roj

题目 ID: 1779

难度:提高+/省选-

标签:动态规划状压DP数位记忆化搜索python

创建: 2026-10-07 11:40

更新: 2026-10-07 11:40

形式化题目

给定一个长度 n≤17n \le 17、只由 0~9 组成且无前导零的字符串 SS,以及正整数 K≤17!K \le 17!。 把 SS 的字符重新排列,得到的所有整数中,筛选出同时满足下面两条的:

  1. 无前导零:最高位不是 00;
  2. 能被 1717 整除:数值 ≡0(mod17)\equiv 0 \pmod{17}。

相同的排列只算一个数(即按不同数值计数)。求这些数中第 KK 小的那个,输出其十进制表示。 数据保证有解。

以样例 S=2242223S = \texttt{2242223}、K=2K = 2 为例:SS 里的数字是五个 2 与两个 3, 用这些数字能拼出的、无前导零且被 1717 整除的数从小到大是 2242232,2242322,…2242232, 2242322, \dots, 第 22 小正是 22422322242232;注意这个数用掉了五个 2 和两个 3,与 SS 的多重集完全一致。

正解

思路

朴素做法与它的瓶颈。 用 next_permutation 从最小排列开始逐个枚举、筛掉前导零, 检查是否被 1717 整除,再去重取第 KK 个。n=17n = 17 时排列数高达 17!≈3.55×101417! \approx 3.55 \times 10^{14}, 当 KK 接近方案总数时必然超时。瓶颈在于:题目要的是「按字典序第 KK 小」, 而我们却把整个决策树都走了一遍——只要能在每个分支上数清「这一支有多少个合法数」, 就能像查字典一样一次只走一条路径。

关键观察一:逐位试填。 求字典序第 KK 小的标准套路是从高位到低位逐位定数: 在第 ii 位从小到大试填合法数字 dd,记「填了 dd 之后,剩余部分能凑出的合法方案数」为 cntcnt, 则

  • K≤cntK \le cnt:目标数的第 ii 位就是 dd,定下它,进入下一位;
  • K>cntK > cnt:这一支的所有数都比答案小,令 K←K−cntK \leftarrow K - cnt,试下一个更大的 dd。

于是问题归约成一个计数问题:给定剩余数字集合与已定前缀,数一数剩下能凑出多少个合法后缀。

关键观察二:状态只需「数字多重集 + 前缀余数」。 因为排列的自由度只取决于「还剩哪些数字」 (而不是它们原来在第几位),所以剩下的部分完全由每个数字的剩余重数刻画,即一个多重集 MS\text{MS}。前缀的影响则只通过它的数值模 1717 的余数 pp 传递,因为后一位填 dd 时 新余数是 (p×10+d) mod 17(p \times 10 + d) \bmod 17——高位的影响可以用一个 0∼160 \sim 16 的小整数吸收掉。

关键观察三:按数字取值分叉就天然去重。 定义

H(MS)[t]=用多重集 MS 里的数字拼出的所有不同字符串中,数值≡t(mod17) 的个数。H(\text{MS})[t] = \text{用多重集 } \text{MS} \text{ 里的数字拼出的所有\emph{不同}字符串中,数值} \equiv t \pmod{17} \text{ 的个数}。

按最低位 dd 递推。设 X=10X′+dX = 10 X' + d,其中 X′X' 由 MS∖{d}\text{MS} \setminus \{d\} 排列而成, 则 X≡t  ⟺  10X′≡t−d  ⟺  X′≡(t−d)⋅10−1(mod17)X \equiv t \iff 10 X' \equiv t - d \iff X' \equiv (t-d) \cdot 10^{-1} \pmod{17}。 在模 1717 下 1010 的逆元是 1212(10×12=120≡110 \times 12 = 120 \equiv 1),于是

H(MS)[t]=∑d∈MSH(MS∖{d})[((t−d) mod 17)⋅12 mod 17],H(∅)[0]=1.H(\text{MS})[t] = \sum_{d \in \text{MS}} H\big(\text{MS} \setminus \{d\}\big)\Big[\big((t-d) \bmod 17\big) \cdot 12 \bmod 17\Big], \qquad H(\varnothing)[0] = 1.

递推里对 dd 的分支只按数字取值枚举,不按字符下标枚举:例如剩下的 2 有 5 份, 写 22222 时无论用哪一份结果都一样,只走一条分支即可。 这样每条「根到叶」的路径与一个不同的字符串一一对应,统计出来的天然是去重后的个数, 不需要再除以 ∏cd!\prod c_d!。

为什么状态数很小。 状态就是一个多重集,用混进制编号 idx=∑d=09cd⋅based\text{idx} = \sum_{d=0}^{9} c_d \cdot \text{base}_d(based=∏e<d(ce+1)\text{base}_d = \prod_{e<d}(c_e + 1))表示, 值域是 0∼∏d(cd+1)−10 \sim \prod_d (c_d + 1) - 1。在 ∑cd≤17\sum c_d \le 17 的约束下, ∏(cd+1)\prod (c_d+1) 在 cdc_d 尽量平均时最大:1717 个数摊到 1010 个数字上约为 27⋅13=1282^7 \cdot 1^3 = 128 量级……实际把所有分配枚举一遍可得上界约 1.2×1041.2 \times 10^4 (例如 c=(2,2,2,2,2,2,2,2,1,0)c = (2,2,2,2,2,2,2,2,1,0) 时乘积 38×2=131223^8 \times 2 = 13122), 再乘上 1717 个余数,DP 表只有十几万个 long long,内存 1 MB 出头。

把计数接到试填上。 设当前已定前缀的值模 1717 为 pp,含当前位还剩 mm 位要定。 试填第 ii 位为 dd 后前缀变成 np=(p×10+d) mod 17np = (p \times 10 + d) \bmod 17,其后还有 m−1m - 1 位, 设后缀拼成的数为 XX,则整个数

V≡np⋅10m−1+X(mod17),V≡0  ⟺  X≡(−np)⋅10m−1(mod17).V \equiv np \cdot 10^{m-1} + X \pmod{17}, \qquad V \equiv 0 \iff X \equiv (-np) \cdot 10^{m-1} \pmod{17}.

所以该分支的合法方案数就是

cnt=H(MS∖{d})[((−np) mod 17)⋅10m−1 mod 17].cnt = H\big(\text{MS} \setminus \{d\}\big)\Big[\big((-np) \bmod 17\big) \cdot 10^{m-1} \bmod 17\Big].

10m−1 mod 1710^{m-1} \bmod 17 提前用长度为 n+1n+1 的数组打表即可。

从样例看一遍。 S=2242223S = \texttt{2242223},故 MS={25,32}\text{MS} = \{2^5, 3^2\},n=7n = 7,K=2K = 2。 最高位只能试 22 或 33(不能是 00,而这里也没有 00):

  • d=2d = 2:np=2np = 2,后缀长度 m−1=6m - 1 = 6,106 mod 17=910^6 \bmod 17 = 9(10k10^k 模 1717 以 10,15,14,4,6,9,5,16,7,…10,15,14,4,6,9,5,16,7,\dots 循环)。 需要 X≡−2⋅9=−18≡16(mod17)X \equiv -2 \cdot 9 = -18 \equiv 16 \pmod{17}。剩余多重集 {24,32}\{2^4, 3^2\} 能凑出的数里余 1616 的个数 至少有 22 个(如 22422322242232 的后缀 242232≡16242232 \equiv 16、22423222242322 的后缀 242322≡16242322 \equiv 16), cnt≥2≥K=2cnt \ge 2 \ge K = 2,所以最高位确定为 2,KK 不变。
  • 之后每一位都重复同样的判定,KK 依次被大于等于它的分支"锁住", 最终输出 2242232,与样例一致。

一句话概括:先用 DP 数清每个多重集能凑出多少合法后缀,再让 KK 带着字典序信息只走一条路。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 11:40
# update_at: 2026-10-07 11:40

import sys
from functools import cache

MOD = 17    # 整除模数
INV10 = 12  # 10 在模 17 下的逆元:10 * 12 = 120 ≡ 1 (mod 17)

type Multiset = tuple[int, ...]  # 数字 0..9 各自剩余的重数,长度为 10
type RemDist = tuple[int, ...]   # 余数分布,下标 t 对应「数值 ≡ t (mod 17)」的个数


@cache
def rem_dist(ms: Multiset) -> RemDist:
    """用 ms 里的数字拼出的所有不同字符串的余数分布。

    按最低位 d 递推:X = 10 * X' + d,X ≡ t 等价于 X' ≡ (t - d) * 10^{-1} (mod 17)。
    分支只按数字取值枚举(不按字符下标),同一数字的多份拷贝不会重复计入,
    因此统计到的天然是「不同字符串」的个数,不需要再除以重数阶乘。
    """
    if not any(ms):                                  # 空多重集:空串的值为 0
        return (1,) + (0,) * (MOD - 1)
    out = [0] * MOD
    for d, c in enumerate(ms):
        if not c:
            continue
        sub = rem_dist(ms[:d] + (c - 1,) + ms[d + 1:])          # 去掉一个 d
        for t in range(MOD):
            out[t] += sub[(t - d) * INV10 % MOD]                # 反推低位之前的余数
    return tuple(out)


def nth_number(ms: Multiset, k: int, n: int, pow10: list[int]) -> str:
    """逐位试填,求满足条件的第 k 小数(前缀 mod 17 记作 p,剩余位数记作 m)。"""
    p, ans = 0, []
    for i in range(n):
        m = n - i                                            # 含当前位在内还剩多少位
        for d in range(10):
            if not ms[d] or (i == 0 and d == 0):             # 没有该数字 / 前导零
                continue
            np = (p * 10 + d) % MOD
            nxt = ms[:d] + (ms[d] - 1,) + ms[d + 1:]
            # 整个数 ≡ np * 10^{m-1} + X,要求 ≡ 0,故后缀 X 必须 ≡ (-np) * 10^{m-1}
            cnt = rem_dist(nxt)[(MOD - np) * pow10[m - 1] % MOD]
            if k > cnt:
                k -= cnt                                     # 这一支的方案全部更小,跳过
                continue
            ans.append(chr(48 + d))
            p, ms = np, nxt
            break                                                # 当前位定下,进入下一位
    return "".join(ans)


def solve() -> None:
    s, K = sys.stdin.buffer.read().split()
    n = len(s)
    digits = [b - 48 for b in s]
    ms = tuple(digits.count(d) for d in range(10))            # 数字多重集

    pow10 = [1] * (n + 1)                                     # 10 的幂(模 17)
    for i in range(1, n + 1):
        pow10[i] = pow10[i - 1] * 10 % MOD

    print(nth_number(ms, int(K), n, pow10))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
// 第K小数(一本通 1779 / JZOJ P3458《密码》同源)
// ---------------------------------------------------------------------------
// 题意:给一个长度 n ≤ 17、由 '0'~'9' 组成且无前导零的字符串 S,把 S 中所有数字
//       重排,得到「无前导零且能被 17 整除」的所有不同整数,求其中第 K 小的那个。
//
// 建模:把「一个数的后缀」抽象成「一个数字多重集」。设
//         H(MS)[t] = 用多重集 MS 里的数字拼出的所有不同字符串中,数值 ≡ t (mod 17) 的个数。
//       按最低位递推:X = 10 * X' + d(d 为最低位,X' 由 MS \ {d} 排列而成),
//         X ≡ t  ⟺  10 * X' ≡ t - d  ⟺  X' ≡ (t - d) * 10^{-1} (mod 17),
//       而 10 在模 17 下的逆元是 12(10 * 12 = 120 ≡ 1),故
//         H(MS)[t] = Σ_{d ∈ MS} H(MS \ {d})[ ((t - d) mod 17) * 12 mod 17 ],
//         H(∅)[0] = 1。
//       分支只按**数字取值**枚举(相同数字只走一条分支),因此统计到的天然是
//       「不同字符串」的个数,不需要再除以重数阶乘去重。
//
// 状态压缩:状态就是一个多重集,用混进制编号 idx = Σ c[d] * base[d](base[d] = ∏_{e<d}(cnt[e]+1))
//       表示,编号范围 0 .. ∏(cnt[d]+1) - 1。n ≤ 17、10 个数字时该乘积的最大值
//       = 3^3 * 2^7 = 17496(重数分布为 (1,1,1,2,2,2,2,2,2,2) 时取到),所以状态表非常小。
//
// 求解:从高位到低位逐位试填。设当前已定前缀模 17 的值为 p、剩余数字个数为 m,
//       试填 d 后前缀变成 np = (p * 10 + d) mod 17,之后还剩 m-1 位要填;
//       设剩余后缀拼成的数为 X,则整个数 ≡ np * 10^{m-1} + X (mod 17),要求 ≡ 0,
//       即 X ≡ (-np) * 10^{m-1} (mod 17),于是该分支的方案数就是
//         cnt = H(MS \ {d})[ ((-np) mod 17) * 10^{m-1} mod 17 ]。
//       若 K > cnt 则 K -= cnt 继续试更大的 d,否则这一位就定为 d。
//       首位(第 1 位)跳过 d = 0,其余位允许 0。
//
// 复杂度:时间 O(状态数 × 17 × 10) ≈ 3e6 次加法,空间 O(状态数 × 17) ≈ 2.4 MB(静态表)。
// ---------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const int MOD = 17;    // 整除模数
static const int INV10 = 12;  // 10 在模 17 下的逆元:10 * 12 = 120 ≡ 1 (mod 17)

static int base10[10];                  // 混进制权重 base[d] = ∏_{e<d} (cnt[e] + 1)
static int radixr[10];                  // radixr[d] = cnt[d] + 1
static const int MAXS = 17500;          // 多重集编号上界:∏(cnt[d]+1) ≤ 17496
static array<ll, MOD> dp[MAXS];         // dp[idx][t]:该多重集的字符串里 ≡ t (mod 17) 的个数
static bool vis[MAXS];                  // 记忆化标记

// 取编号 idx 所代表的多重集中数字 d 的重数
static inline int getCnt(int idx, int d) { return (idx / base10[d]) % radixr[d]; }

// 记忆化:算出编号 idx 对应多重集的 dp[idx][0..16]
static void dfs(int idx) {
    if (vis[idx]) return;
    vis[idx] = true;
    if (idx == 0) {                     // 空多重集:空串数值为 0
        dp[0][0] = 1;
        return;
    }
    for (int d = 0; d < 10; d++) {
        if (getCnt(idx, d) == 0) continue;   // 该数字已用完
        int sub = idx - base10[d];           // 去掉一个 d 后的多重集编号
        dfs(sub);
        for (int t = 0; t < MOD; t++) {
            int src = ((t - d) % MOD + MOD) % MOD * INV10 % MOD;  // X' 需要的余数
            dp[idx][t] += dp[sub][src];
        }
    }
}

int main() {
    string s;
    ll K;
    if (!(cin >> s >> K)) return 0;

    int n = (int)s.size();
    int cnt[10] = {0};
    for (int i = 0; i < n; i++) cnt[s[i] - '0']++;

    // 混进制编号:idx = Σ cntUsed[d] * base10[d]
    int weight = 1;
    for (int d = 0; d < 10; d++) {
        base10[d] = weight;
        radixr[d] = cnt[d] + 1;
        weight *= radixr[d];
    }
    int full = 0;                                  // 初始(完整)多重集的编号
    for (int d = 0; d < 10; d++) full += cnt[d] * base10[d];

    // 10 的幂(模 17),10^k mod 17
    ll pow10mod[20];
    pow10mod[0] = 1;
    for (int i = 1; i <= n; i++) pow10mod[i] = pow10mod[i - 1] * 10 % MOD;

    dfs(full);                                     // 预处理所有子多重集的方案数

    int idx = full;                                // 当前剩余多重集的编号
    int p = 0;                                     // 已定前缀模 17 的值
    string ans;
    for (int i = 0; i < n; i++) {
        int m = n - i;                             // 当前还剩多少位要确定
        for (int d = 0; d < 10; d++) {
            if (getCnt(idx, d) == 0) continue;     // 剩余数字里没有 d
            if (i == 0 && d == 0) continue;        // 无前导零
            int np = (p * 10 + d) % MOD;
            int need = (int)((ll)((MOD - np) % MOD) * pow10mod[m - 1] % MOD);
            int sub = idx - base10[d];
            ll cur = dp[sub][need];                // 该分支能凑出的方案数
            if (K > cur) {
                K -= cur;                          // 这一支全部太小,跳过
            } else {
                ans.push_back(char('0' + d));
                p = np;
                idx = sub;
                break;
            }
        }
    }
    printf("%s\n", ans.c_str());
    return 0;
}

Python 版的状态直接用 tuple[int, ...](10 个数字的重数)当 @cache 的键, 省掉手工进制编码;C++ 版为了 O(1) 访问用混进制整数编号,配合 dp[13000][17] 的静态表。

复杂度

  • 时间:DP 部分共 ∏d(cd+1)⋅17≤1.3×104×17≈2.2×105\prod_d (c_d + 1) \cdot 17 \le 1.3 \times 10^4 \times 17 \approx 2.2 \times 10^5 个状态值,每个状态最多枚举 1010 个数字、每个数字累加 1717 个余数, 总加法量约 10×17×1.3×104≈2.2×10610 \times 17 \times 1.3 \times 10^4 \approx 2.2 \times 10^6。 逐位试填只有 n×10n \times 10 次查表,可忽略。实测远低于 1000 ms 限制。
  • 空间:DP 表 ∏(cd+1)×17\prod (c_d+1) \times 17 个 64 位整数,约 1.3×104×17×8≈1.81.3 \times 10^4 \times 17 \times 8 \approx 1.8 MB, 远低于 256 MB。Python 版用 dict 记忆化,占用同阶。
  • 与 C++ 解法的关系:两者是同阶算法,只是状态编码方式不同; Python 版用元组当字典键、靠 @cache 记忆化,代码更短,规模上限一样时略慢但完全够用。

总结

  • 第 KK 小 = 逐位试填 + 分支计数。把"搜整棵树"换成"每个分支数一次", 复杂度从 O(n!)O(n!) 降到 O(状态数×17×10)O(\text{状态数} \times 17 \times 10)。
  • 让状态吸收掉历史。一位一位往后走时,前缀的全部影响只剩一个余数 pp—— 模数是 1717 这种小常数时,这类"把前缀压进余数"的写法是把排列问题变成 DP 的关键。
  • 按"值"分叉而不是按"位置"分叉。多重集中相同数字的字符互相不可区分, 只在数字取值上分叉,重复计数就自动消失,比"先按位置数再除以重数阶乘"更省事也更不容易错。
  • 逆元把"向前看"变成"向后推"。X=10X′+dX = 10X' + d 是向前构造,而 DP 是从短串往长串递推的, 用 10−1≡12(mod17)10^{-1} \equiv 12 \pmod{17} 把目标余数反推回短串即可,是整除类数位 DP 的常用手法。
  • 数据说明:本题素材源中带有数据生成脚本 data.py,说明随仓 data/ 是自造的, 题面系按公开原题(一本通 1779 / JZOJ P3458《密码》)重建,出题意图与官方原题可能存在偏差; 本文的算法与实现以题面描述和随仓数据的实测结果为准。