错排序列第N项模M=?

Question

错排递推式：f(n)=(n-1)*(f(n-1)+f(n-2)) f(1)=0,f(2)=1

求f(n)%m,m<=1e5,n<=1e9,n,m为整数。

网上有人说循环节长度为2*m,起始位置是f(1)，所以直接求f(n%(2*m))。对吗？为什么。

Answer 1

~~~ #UPDATE: 又仔细想了下 最后推导似乎有问题 略囧 所以仅供参考思路了 ~~~

----

你给出的这个“错排递推公式”，实际上有一个“直接”的计算公式：

f(n) =  n! * ((-1)^0/0! + (-1)^1 / 1! + (-1)^2 / 2! + ... + (-1)^n*1/n!)

已知

x = aX + b
y = cY + d
(x + y) % m = (aX + b + cY + d) % m = (b + d) % m = (X % m + Y % m) % m

记

g(n) = f(n) % m

则有

g(2m + n) = ((2m + n)! * (
[1]      -1^0    / 0!    + (-1)^1      / 1!      + ... + (-1)^(m-1)  / (m-1)!
[2]  + (-1)^m    / m!    + (-1)^(m+1)  / (m+1)!  + ... + (-1)^(2m-1) / (2m-1)!
[3]  + (-1)^(2m) / (2m)! + (-1)^(2m+1) / (2m+1)! + ... + (-1)^(2m+n) / (2m+n)!
    )) % m

由于 ((2m + n)! * 任意一个前2m项) % m == 0，所以前两行可以消掉(这个很容易看出来的吧？)

g(2m + n) 
  = ((2m + n)! * (
      (-1)^(2m) / (2m)! + (-1)^(2m+1) / (2m+1)! + ... + (-1)^(2m+n) / (2m+n)!
     )) % m
~~~ 由于 (-1)^2m == 1 ~~~
  = ((2m + n)! * (
      (-1)^0 / (2m)! + (-1)^1 / (2m+1)! + ... + (-1)^n / (2m+n)!
     )) % m
  = ((-1)^0 / n! + (-1)^1 / (n-1)! + ... + (-1)^n / 0!) % m

这里已经很接近你说的结论了，由于n是奇偶的时候会影响这里的正负号，而我前面没有证明 (x - y) % m 的公式，但是由于实际上前2m项减去后n项毫无疑问是正数（中间这些琐碎的证明略掉），所以最终结论就是：

 g(2m + n) == g(n) 

Answer 2

循环节不超过m^2。（因为f[n]由f[n-1],f[n-2]唯一决定，在mod m下f[n-1]和f[n-2]最多有m^2种组合。）

一边开哈希表一这算递推，算到出现循环为止。注意循环节可能到中间才出现（想想循环小数）。