錯排遞推式：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 回答
忽然笑
TA貢獻1806條經驗 獲得超5個贊
循環節不超過m^2。（因為f[n]由f[n-1],f[n-2]唯一決定，在mod m下f[n-1]和f[n-2]最多有m^2種組合。）
一邊開哈希表一這算遞推，算到出現循環為止。注意循環節可能到中間才出現（想想循環小數）。
開滿天機
TA貢獻1786條經驗 獲得超13個贊
你給出的這個“錯排遞推公式”，實際上有一個“直接”的計算公式：
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)
添加回答
舉報
0/150
提交
取消