0w1

TOI 排隊約瑟夫問題 ( DP + 代數分析 )

每次審判排頭有 d的機率死亡並被逐出隊伍,否則則返回隊尾。當排頭是最後一個人的時候審判不會再進行。
f:id:h0rnet:20160302224341p:plain
現在給你隊伍初始的人數 n,你的編號 k( 注意 0 ≤ k < n ),審判的死亡機率 d。
你存活( 成為隊伍裡最後的人 )的機率為多少?
f:id:h0rnet:20160302224706p:plain
我們先令 P( i )為隊伍裡有 i人的情況下,自己是第一個待審判的人時,自己的存活機率。
f:id:h0rnet:20160302225246p:plain
首先邊界 P( 1 )很明顯是 1
f:id:h0rnet:20160302225307p:plain
P( i )的遞迴關係可以看成是這樣子的狀態之間的轉移,每個轉移邊也都有各自的權重( 轉移機率 )
f:id:h0rnet:20160302234214p:plain
注意到狀態的遷移邊含有自環,無法做遞推,我們必須要想辦法除去它。
首先構造遞迴式
{ \displaystyle
P( i ) = \sum_{j=1}^{i} P( j ) * w( i, j )
}
{ \displaystyle
其中 w( i, j ) 表示由 i人在隊伍裡且自己是待審判的排頭 轉移到 j人在隊伍裡且自己是待審判的排頭的機率
}
我們可以考慮把第 i項提出來
{ \displaystyle
P( i ) = \sum_{j=1}^{i-1} P( j ) * w( i, j ) + P( i ) * w( i, i )
}
{ \displaystyle
(\ 1 - w( i, i )\ ) * P( i ) = \sum_{j=1}^{i-1} P( j ) * w( i, j )
}
{ \displaystyle
P( i ) = (\ \sum_{j=1}^{i-1} P( j ) * w( i, j )\ ) \ /\  (\ 1 - w( i, i )\ )
}
這麼一來就能確實地做遞推了。順帶一提,w( i, j )可以根據 dw( i, j )計算
{ \displaystyle
dw( i, j ):\ i個人被審判後,其中\ j人死亡的機率
}
{ \displaystyle
dw( 0, 0 ) = 1\\
dw( 1, 0 ) = 1 - d\\
dw( 1, 1 ) = d\\
dw( i, j ) = dw( i - 1, j - 1 ) * d + dw( i - 1, j ) * ( 1 - d )
}
最後回到原本的問題,我們初始是隊伍裡的第 k個人,那麼我們就總和所有自己從第 k個人成為排頭的情況的機率就行了。也就是說,初始時前面有 k個人,那麼我們枚舉所有 m,代表前面 k人中的死亡人數,算出每種情況的權重,套上 P函數計算總和。
f:id:h0rnet:20160302232450p:plain
{ \displaystyle
Ans = \sum_{m=0}^{k} P( n - m ) * dw( k, m )
}
以上就是個比較簡單的 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

*/