algorithm - 计算给定多组数字的第 K 次字典排列形成的数

Question

你有 Q 个问题。每个查询都会为您提供一个由数字 0 到 9 组成的多重集 S 和一个整数 k。您需要确定 S 的 k-th 字典排列的整数表示，模 10^9+7。

限制和其他注意事项:

• k<=10¹²

• Q<=5000

• S 最多包含 70.000 个数字

• 由n阶排列表示的整数，p={p_n-1,p_n-2,...,p₁,p₀}等于p_i*10ⁱ之和，对于0到n的所有i -1。例如，排列 {2,0,1} 给出整数 201。排列也可以以多个 0 开头，例如，排列 {0,0,0,1,2} 将给出整数 12。

• 限时2秒

一些例子:

• 对于 S={0,1},k=1，结果将为 1。

• 对于 S={0,1},k=2: 10

• 对于 S={0,1,2},k=1: 12

• 对于 S={0,1,2},k=2: 21

• 对于 S={0,1,2},k=5: 201

• 对于 S={0,1,1},k=2: 101

我在寻找足够有效的解决方案时遇到了问题。我尝试通过通常的方法找到第 k 个排列，然后简单地计算模数，但速度不够快。我认为模数确实改变了很多东西。

我还观察到，与可能的排列数相比，k 相对较小，因此这可能为一些优化腾出空间。

Answer 1

I tried finding the k-th permutation via the usual method

不确定您常用的方法是什么。可以在 O(|S|) 时间内获得第 k 个排列，我假设您正在使用它。

then simply calculating the modulo, but it isn't fast enough

请注意，对于多个查询，您具有相同大小的 S。您应该构建数组 D，D[i] = 10^i % M，然后对于每个给定的排列，只需找到 D[i]*S[p[i]] % M 的总和 - 再次，线性时间。

实际上因为 k < 15!只有最后 15 位数字改变了它们的顺序，对于所有查询，它们之前的所有内容只需计算一次。