错排递推式: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))
。对吗?为什么。
错排递推式: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))
。对吗?为什么。
循环节不超过m^2。(因为f[n]由f[n-1],f[n-2]唯一决定,在mod m下f[n-1]和f[n-2]最多有m^2种组合。)
一边开哈希表一这算递推,算到出现循环为止。注意循环节可能到中间才出现(想想循环小数)。
1 回答3.3k 阅读✓ 已解决
1 回答2.8k 阅读
2.5k 阅读
1 回答524 阅读✓ 已解决
1 回答1.1k 阅读
1 回答482 阅读✓ 已解决
~~~ #UPDATE: 又仔细想了下 最后推导似乎有问题 略囧 所以仅供参考思路了 ~~~
----
你给出的这个“错排递推公式”,实际上有一个“直接”的计算公式:
已知
记
则有
由于 ((2m + n)! * 任意一个前2m项) % m == 0,所以前两行可以消掉(这个很容易看出来的吧?)
这里已经很接近你说的结论了,由于n是奇偶的时候会影响这里的正负号,而我前面没有证明 (x - y) % m 的公式,但是由于实际上前2m项减去后n项毫无疑问是正数(中间这些琐碎的证明略掉),所以最终结论就是: