TOI 排隊約瑟夫問題 ( DP + 代數分析 )
每次審判排頭有 d的機率死亡並被逐出隊伍,否則則返回隊尾。當排頭是最後一個人的時候審判不會再進行。
現在給你隊伍初始的人數 n,你的編號 k( 注意 0 ≤ k < n ),審判的死亡機率 d。
你存活( 成為隊伍裡最後的人 )的機率為多少?
我們先令 P( i )為隊伍裡有 i人的情況下,自己是第一個待審判的人時,自己的存活機率。
首先邊界 P( 1 )很明顯是 1
P( i )的遞迴關係可以看成是這樣子的狀態之間的轉移,每個轉移邊也都有各自的權重( 轉移機率 )
注意到狀態的遷移邊含有自環,無法做遞推,我們必須要想辦法除去它。
首先構造遞迴式
我們可以考慮把第 i項提出來
這麼一來就能確實地做遞推了。順帶一提,w( i, j )可以根據 dw( i, j )計算
最後回到原本的問題,我們初始是隊伍裡的第 k個人,那麼我們就總和所有自己從第 k個人成為排頭的情況的機率就行了。也就是說,初始時前面有 k個人,那麼我們枚舉所有 m,代表前面 k人中的死亡人數,算出每種情況的權重,套上 P函數計算總和。
以上就是個比較簡單的 O( n ^ 2 )做法,歡迎提供更好的方法。
註:以下代碼未經過嚴密測試,如果有找到瑕疵請務必和我聯絡,謝謝!
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 4; const int MAXK = MAXN; int n, k; double d; // dw[ i ][ j ]: probability of i people try, j people die double dw[ MAXN ][ MAXN ]; void precomputeDieWeight(){ memset( dw, 0, sizeof(dw) ); dw[ 0 ][ 0 ] = 1.0; dw[ 1 ][ 0 ] = 1.0 - d; dw[ 1 ][ 1 ] = d; for(int i = 1; i < n; ++i) for(int j = 0; j <= i; ++j){ dw[ i + 1 ][ j ] += dw[ i ][ j ] * ( 1.0 - d ); dw[ i + 1 ][ j + 1 ] += dw[ i ][ j ] * d; } } // p[ i ]: now i people are in queue, survivability of first person double p[ MAXN ]; void precomputeP(){ memset( p, 0, sizeof(p) ); p[ 1 ] = 1.0; for(int i = 2; i <= n; ++i){ // how many people in queue double s = 0.0; for(int j = 1; j <= i - 1; ++j){ // j: total alive double weight = ( 1.0 - d ) * dw[ i - 1 ][ i - j ]; s += p[ j ] * weight; } p[ i ] = s / ( 1.0 - dw[ i ][ 0 ] ); } } void solve(){ precomputeDieWeight(); precomputeP(); double ans = 0.0; for(int m = 0; m <= k; ++m) ans += p[ n - m ] * dw[ k ][ m ]; printf("%.10lf\n", ans); } int main(){ while( scanf("%d%d%lf", &n, &k, &d) == 3 ){ assert( 1 <= n && n < MAXN ); assert( 0 <= k && k < n ); assert( 0.0 <= d && d <= 1.0 ); solve(); } return 0; } /* input: 1 0 0.5 2 0 0.5 2 1 0.5 4 0 0.5 4 1 0.5 4 2 0.5 4 3 0.5 4 0 0.1 4 1 0.1 4 2 0.1 4 3 0.1 output: 1.0000000000 0.3333333333 0.6666666667 0.1809523810 0.2095238095 0.2476190476 0.3619047619 0.2372814976 0.2451905589 0.2538818351 0.2636461084 */