阶乘反元素取模质数 (!n mod p)

Question

是否有一种简单的方法来实现 !n mod p (错排数量)，其中 n ≤ 2∗10^8，p 是质数且 p < 1000。

程序必须执行快速，因此朴素方法行不通。

- user1721258

---

出于好奇，这是哪个 SPOJ 问题？ - Nabb

由于 p < 1000，因此值得研究错排是否在模 p 下是周期性的。例如，前几个数 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932 在模 2 下具有周期为 2 的特点：奇偶奇偶...；我相信这种情况会一直持续下去，并适用于其他数字。 - IVlad

!n mod p 看起来是以周期 2p（对于奇数 p）出现的，因此这提供了一个直接的算法来计算所需的值。不过，你可能想要尝试证明这种周期性。 - Nabb

@Nabb 它在波兰的SPOJ上，网址为http://pl.spoj.pl/problems/LETTERS5/。 - user1721258

@BugMeNot 我发现这个关系是有效的。!n = floor(n!/e)。递归阶乘将需要 O(log N) 的时间。 - venkatKA

Answer 1

原来，!n mod p 的周期为 2p。因此，我们可以将 !n mod p 计算为 !(n mod 2p) mod p，并使用错排的递归公式 !n = (n-1) (!(n-1) + !(n-2)) 进行计算。

证明如下：

• 观察到根据错排的递归关系，!(p+1) = 0 mod p。
• 在模 p 的情况下，!(n+p) = !p * !n（可以通过使用前面的观察结果进行归纳证明）。
• 观察到 !p = -1 mod p。维基百科提供了一个公式：!n = n! - Sum[(n choose i) * !(n-i), i=1..n]，在模 p 的情况下，右侧唯一非零项出现在 i=n 处。
• 得出结论： !(n+2p) = !p !p !n = !n mod p。

从证明中，我们可以看到实际上可以计算 !n = ± !(n mod p) mod p，其中当 n mod 2p 小于 p 时，符号为正。

- Nabb

Answer 2

既然有递归公式 (!n = (n - 1) (!(n-1) + !(n-2)))，为什么不实现“模 p 的乘法”和“模 p 的加法”操作呢？

- Vlad

---

对于这么大的 n？太慢了。 - IVlad

@Vlad：我觉得太慢了，因为它可能需要大约 400M 次操作。 - Steve Jessop

执行时间大约为0.2秒，n次乘法将会花费太长时间。我相信有一些聪明的方法可以减少问题，因为p的限制是p < 1000。 - user1721258

@BugMeNot - 这是一个非常重要的限制！请将其与任何其他信息一起添加到 OP 中。 - IVlad

经过考虑，这个关系可能是一个有效的前进方式。如果你记忆化函数 f(a,b,c) { return (a-1)(b + c) % p}，那么在给定 p < 1000 的情况下，你最多需要十亿个值。但是 Nabb 上面观察到 !n mod p 看起来是循环的，周期比那还要短，所以实际上你需要的值更少。再加上一些循环检测，你可能可以很快得到该值。而且这还没有进行任何数学计算——提前证明某个漂亮的公式，如 2*p 的循环长度，虽然更好，但在0.2秒的时间限制内可能并不必要 :-) - Steve Jessop

@Steve：记忆化一个只执行3个算术操作的函数？真的吗？ ;) - Niklas B.