把「剩余数字多重集」当状态预处理余数分布,再按位试填,用可被 17 整除的后缀方案数逼近第 K 小数。
OJ: roj
题目 ID: 1779
难度:提高+/省选-
标签:动态规划状压DP数位记忆化搜索python
创建: 2026-10-07 11:40
更新: 2026-10-07 11:40
形式化题目
给定一个长度 0~9 组成且无前导零的字符串
- 无前导零:最高位不是
; - 能被
整除:数值 。
相同的排列只算一个数(即按不同数值计数)。求这些数中第
以样例 2 与两个 3,
用这些数字能拼出的、无前导零且被 2 和两个 3,与
正解
思路
朴素做法与它的瓶颈。 用 next_permutation 从最小排列开始逐个枚举、筛掉前导零,
检查是否被
关键观察一:逐位试填。 求字典序第
:目标数的第 位就是 ,定下它,进入下一位; :这一支的所有数都比答案小,令 ,试下一个更大的 。
于是问题归约成一个计数问题:给定剩余数字集合与已定前缀,数一数剩下能凑出多少个合法后缀。
关键观察二:状态只需「数字多重集 + 前缀余数」。 因为排列的自由度只取决于「还剩哪些数字」
(而不是它们原来在第几位),所以剩下的部分完全由每个数字的剩余重数刻画,即一个多重集
关键观察三:按数字取值分叉就天然去重。 定义
按最低位
递推里对 2 有 5 份,
写 22222 时无论用哪一份结果都一样,只走一条分支即可。
这样每条「根到叶」的路径与一个不同的字符串一一对应,统计出来的天然是去重后的个数,
不需要再除以
为什么状态数很小。 状态就是一个多重集,用混进制编号
long long,内存 1 MB 出头。
把计数接到试填上。 设当前已定前缀的值模
所以该分支的合法方案数就是
从样例看一遍。
: ,后缀长度 , ( 模 以 循环)。 需要 。剩余多重集 能凑出的数里余 的个数 至少有 个(如 的后缀 、 的后缀 ), ,所以最高位确定为 2,不变。 - 之后每一位都重复同样的判定,
依次被大于等于它的分支"锁住", 最终输出 2242232,与样例一致。
一句话概括:先用 DP 数清每个多重集能凑出多少合法后缀,再让
代码
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++ 版(同一算法):
// 第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 部分共
个状态值,每个状态最多枚举 个数字、每个数字累加 个余数, 总加法量约 。 逐位试填只有 次查表,可忽略。实测远低于 1000 ms 限制。 - 空间:DP 表
个 64 位整数,约 MB, 远低于 256 MB。Python 版用 dict记忆化,占用同阶。 - 与 C++ 解法的关系:两者是同阶算法,只是状态编码方式不同;
Python 版用元组当字典键、靠
@cache记忆化,代码更短,规模上限一样时略慢但完全够用。
总结
- 第
小 = 逐位试填 + 分支计数。把"搜整棵树"换成"每个分支数一次", 复杂度从 降到 。 - 让状态吸收掉历史。一位一位往后走时,前缀的全部影响只剩一个余数
—— 模数是 这种小常数时,这类"把前缀压进余数"的写法是把排列问题变成 DP 的关键。 - 按"值"分叉而不是按"位置"分叉。多重集中相同数字的字符互相不可区分, 只在数字取值上分叉,重复计数就自动消失,比"先按位置数再除以重数阶乘"更省事也更不容易错。
- 逆元把"向前看"变成"向后推"。
是向前构造,而 DP 是从短串往长串递推的, 用 把目标余数反推回短串即可,是整除类数位 DP 的常用手法。 - 数据说明:本题素材源中带有数据生成脚本
data.py,说明随仓data/是自造的, 题面系按公开原题(一本通 1779 / JZOJ P3458《密码》)重建,出题意图与官方原题可能存在偏差; 本文的算法与实现以题面描述和随仓数据的实测结果为准。