是否有一种简单的方法来实现 !n mod p
(错排数量),其中 n ≤ 2∗10^8
,p
是质数且 p < 1000
。
程序必须执行快速,因此朴素方法行不通。
!n mod p
的周期为 2p
。因此,我们可以将 !n mod p
计算为 !(n mod 2p) mod p
,并使用错排的递归公式 !n = (n-1) (!(n-1) + !(n-2))
进行计算。!(p+1) = 0 mod 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
时,符号为正。既然有递归公式 (!n = (n - 1) (!(n-1) + !(n-2))
),为什么不实现“模 p
的乘法”和“模 p
的加法”操作呢?
n
?太慢了。 - IVladf(a,b,c) { return (a-1)(b + c) % p}
,那么在给定 p < 1000
的情况下,你最多需要十亿个值。但是 Nabb 上面观察到 !n mod p
看起来是循环的,周期比那还要短,所以实际上你需要的值更少。再加上一些循环检测,你可能可以很快得到该值。而且这还没有进行任何数学计算——提前证明某个漂亮的公式,如 2*p
的循环长度,虽然更好,但在0.2秒的时间限制内可能并不必要 :-) - Steve Jessop
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!n = floor(n!/e)
。递归阶乘将需要 O(log N) 的时间。 - venkatKA