c++ - 有效地计算阶乘

Question

我有一个 N 最多为 10^5 的数组。我需要使用给定的 L 和 R 解决 Q 范围查询。Q <= 10^5

对于每个查询，我需要在 L 到 R 范围内找到不同的元素然后找到它们的阶乘。

例如，如果数组是 {5, 4, 2, 4, 5, 5, 7}。

如果 L = 2 且 R = 4。

然后我们有 { 4 : 2 times, 2: 1 time }，所以答案是 (2!)*(1!) = 2。

如果 L = 1 且 R = 5然后我们有 {5 : 2 times, 4: 2 times, 2 : 1 time}，所以答案是 (2!)*(2!).(1!) = 4 .

O((N)*(Q)) 这个问题的解决方案是显而易见的。我该如何优化它。

注意:所有阶乘均以 1000000007 为模计算

Answer 1

好的，因为(根据您的评论)，数组中只能有 10⁵ 个元素，这也是数组中每个可能值的最大计数 .

因此，您可以做的一件事是将所有这些阶乘预先计算到一个数组中，然后使用它们进行计算。

可能最好的方法是编写一个元程序，将值构造成 C++ 结构，然后您可以将其包含在自己的代码中^(a)。该结构看起来像:

unsigned int facMod10p7[] = {
    0,
    1,
    2,
    :
    /* whatever (10^5)! % 1000000007 is */
};

一旦你有了它，每个阶乘的查找就是 O(1)。要执行查询方面的操作，您只需遍历数组(从 L 到 R)，计算唯一值的数量。

这可能最好用 map<unsigned int, unsigned int> 来完成第一个字段是值(假设这里的值是无符号的，但你可以很容易地让它有符号)，第二个是它发生的次数。

对于 L2/R4案例{4, 2, 4} ，你最终会得到一张 map :

{ [2] = 1, [4] = 2 }

然后只需遍历查找每个计数的阶乘并获取它们的乘积即可。

由于它是 O(n) 循环内的 O(1) 查找/乘法，因此产生的复杂度为 O(n)。

---

^(a) 例如，一个输出前 10,000 个阶乘的 Python 程序在我的盒子上需要大约 30 秒才能生成整个表格(在我的 WSL 环境中，不一定以其令人眼花缭乱的 I/O 速度，至少在即将发布的下一个版本之前):

real 0m29.137s
user 0m28.438s
sys  0m0.547s

代码，如果你想做自己的测试，是:

print('static unsigned int facMod10p7[] = {\n    0,')
val = 1
mult = 2
for i in range(100000):
    print('    {},'.format(val) % 1000000007)
    val *= mult
    mult += 1
print(');')