有人说循环节长度为2*m,起始位置是f(1)，所以直接求f(n%(2*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为整数。

Answer 1

循环节不超过m^2。（因为f[n]由f[n-1],f[n-2]唯一决定，在mod m下f[n-1]和f[n-2]最多有m^2种组合。）一边开哈希表一这算递推，算到出现循环为止。注意循环节可能到中间才出现（想想循环小数）。

Answer 2

你给出的这个“错排递推公式”，实际上有一个“直接”的计算公式：f(n)&nbsp;=&nbsp;&nbsp;n!&nbsp;*&nbsp;((-1)^0/0!&nbsp;+&nbsp;(-1)^1&nbsp;/&nbsp;1!&nbsp;+&nbsp;(-1)^2&nbsp;/&nbsp;2!&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^n*1/n!)已知x&nbsp;=&nbsp;aX&nbsp;+&nbsp;b y&nbsp;=&nbsp;cY&nbsp;+&nbsp;d(x&nbsp;+&nbsp;y)&nbsp;%&nbsp;m&nbsp;=&nbsp;(aX&nbsp;+&nbsp;b&nbsp;+&nbsp;cY&nbsp;+&nbsp;d)&nbsp;%&nbsp;m&nbsp;=&nbsp;(b&nbsp;+&nbsp;d)&nbsp;%&nbsp;m&nbsp;=&nbsp;(X&nbsp;%&nbsp;m&nbsp;+&nbsp;Y&nbsp;%&nbsp;m)&nbsp;%&nbsp;m记g(n)&nbsp;=&nbsp;f(n)&nbsp;%&nbsp;m则有g(2m&nbsp;+&nbsp;n)&nbsp;=&nbsp;((2m&nbsp;+&nbsp;n)!&nbsp;*&nbsp;( [1]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-1^0&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp;0!&nbsp;&nbsp;&nbsp;&nbsp;+&nbsp;(-1)^1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp;1!&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^(m-1)&nbsp;&nbsp;/&nbsp;(m-1)! [2]&nbsp;&nbsp;+&nbsp;(-1)^m&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp;m!&nbsp;&nbsp;&nbsp;&nbsp;+&nbsp;(-1)^(m+1)&nbsp;&nbsp;/&nbsp;(m+1)!&nbsp;&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^(2m-1)&nbsp;/&nbsp;(2m-1)! [3]&nbsp;&nbsp;+&nbsp;(-1)^(2m)&nbsp;/&nbsp;(2m)!&nbsp;+&nbsp;(-1)^(2m+1)&nbsp;/&nbsp;(2m+1)!&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^(2m+n)&nbsp;/&nbsp;(2m+n)! &nbsp;&nbsp;&nbsp;&nbsp;))&nbsp;%&nbsp;m由于 ((2m + n)! * 任意一个前2m项) % m == 0，所以前两行可以消掉(这个很容易看出来的吧？)g(2m&nbsp;+&nbsp;n)&nbsp; &nbsp;&nbsp;=&nbsp;((2m&nbsp;+&nbsp;n)!&nbsp;*&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-1)^(2m)&nbsp;/&nbsp;(2m)!&nbsp;+&nbsp;(-1)^(2m+1)&nbsp;/&nbsp;(2m+1)!&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^(2m+n)&nbsp;/&nbsp;(2m+n)! &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;))&nbsp;%&nbsp;m~~~&nbsp;由于&nbsp;(-1)^2m&nbsp;==&nbsp;1&nbsp;~~~ &nbsp;&nbsp;=&nbsp;((2m&nbsp;+&nbsp;n)!&nbsp;*&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-1)^0&nbsp;/&nbsp;(2m)!&nbsp;+&nbsp;(-1)^1&nbsp;/&nbsp;(2m+1)!&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^n&nbsp;/&nbsp;(2m+n)! &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;))&nbsp;%&nbsp;m &nbsp;&nbsp;=&nbsp;((-1)^0&nbsp;/&nbsp;n!&nbsp;+&nbsp;(-1)^1&nbsp;/&nbsp;(n-1)!&nbsp;+&nbsp;...&nbsp;+&nbsp;(-1)^n&nbsp;/&nbsp;0!)&nbsp;%&nbsp;m这里已经很接近你说的结论了，由于n是奇偶的时候会影响这里的正负号，而我前面没有证明 (x - y) % m 的公式，但是由于实际上前2m项减去后n项毫无疑问是正数（中间这些琐碎的证明略掉），所以最终结论就是：&nbsp;g(2m&nbsp;+&nbsp;n)&nbsp;==&nbsp;g(n)