错排递推式：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))。对吗？为什么。
~~~ #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)
循环节不超过m^2。（因为f[n]由f[n-1],f[n-2]唯一决定，在mod m下f[n-1]和f[n-2]最多有m^2种组合。）
一边开哈希表一这算递推，算到出现循环为止。注意循环节可能到中间才出现（想想循环小数）。