错排序列第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+by=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]唯一决定，在modm下f[n-1]和f[n-2]最多有m^2种组合。）一边开哈希表一这算递推，算到出现循环为止。注意循环节可能到中间才出现（想想循环小数）。