隨手coding筆記 by波路特石

原題連結： https://tioj.ck.tp.edu.tw/problems/1545 這題看完第一直覺是令$\color{white}{\space dp[N][M]\space}$為輸入$\color{white}{\space N,M\space}$時的答案，可以很輕易的發現轉移是$\color{white}{\space O(N)\space}$。 複雜度$\color{white}{\space O(N^3)\space}$，可以拿下前兩筆subtask。 不過適當的利用精度捨棄不必要的運算之後可以利用這個方法拿到第三筆subtask。 但最終還是過不了第四筆QQ。 稍微被劇透一下解之後，得知若令$\color{white}{\space dp[N]\space}$為輸入$\color{white}{\space N,N\space}$時的答案，則有等式： $\color{white}{\space dp[i]=\frac{1}{2}\displaystyle\sum_{j=0}^{i-2}(\frac{\dbinom{n-1}{j}}{2^{n-1}}dp[i-j])+\frac{\dbinom{n-1}{n-1}}{2^{n-1}}\space}$ 轉移想法來源為，枚舉閃電傳完一輪後(第$\color{white}{\space N\space}$個人傳完)，已經有$\color{white}{\space j\space}$個人被殺掉且第$\color{white}{\space N\space}$個人還活著的機率(多乘一個$\color{white}{\space \frac{1}{2}\space}$)總和起來，但必需特判剛好傳完一輪其他人全死光的情況(此時第$\color{white}{\space N\space}$個人不需要再進行閃電判斷)。 所以稍微做個移項之後可得： $\color{white}{\space (2-\frac{\dbinom{n-1}{0}}{2^{n-1}})dp[i]=\displaystyle\sum_{j=1}^{i-2}(\frac{\dbinom{n-1}{j}}{2^{n-1}}dp[i-j])+2\frac{\dbinom{n-1}{n-1}}{2^{n-1}}\sp...