~~~#UPDATE:又仔細(xì)想了下最后推導(dǎo)似乎有問題略囧所以僅供參考思路了~~~----你給出的這個(gè)“錯(cuò)排遞推公式”，實(shí)際上有一個(gè)“直接”的計(jì)算公式：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(shù)(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)!*任意一個(gè)前2m項(xiàng))%m==0，所以前兩行可以消掉(這個(gè)很容易看出來的吧？)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這里已經(jīng)很接近你說的結(jié)論了，由于n是奇偶的時(shí)候會(huì)影響這里的正負(fù)號(hào)，而我前面沒有證明(x-y)%m的公式，但是由于實(shí)際上前2m項(xiàng)減去后n項(xiàng)毫無疑問是正數(shù)（中間這些瑣碎的證明略掉），所以最終結(jié)論就是：g(2m+n)==g(n)
                            

循環(huán)節(jié)不超過m^2。（因?yàn)閒[n]由f[n-1],f[n-2]唯一決定，在modm下f[n-1]和f[n-2]最多有m^2種組合。）一邊開哈希表一這算遞推，算到出現(xiàn)循環(huán)為止。注意循環(huán)節(jié)可能到中間才出現(xiàn)（想想循環(huán)小數(shù)）。