1. 题目描述
一个长度为n个队列，每次取队头的4个人玩儿游戏，每个人等概率赢得比赛。胜者任然处在队头，然而败者按照原顺序依次排在队尾。连续赢得m场比赛的玩家赢得最终胜利。
求第k个人赢得最终胜利的概率。
2. 基本思路
显然是个概率DP，dp[i][j]表示第1个玩家已经连续赢得i局比赛时，第j个人赢得最终胜利的概率。所求极为dp[0][k]。
\[
dp[m][j] = \begin{cases}
\begin{aligned}
&1, j=1 \\
&0, j>1
\end{aligned}
\end{cases}
\]
$dp[i][j] =$
\[
\quad \left\{ \begin{aligned}
&\frac{1}{4}dp[i+1][j] + \frac{3}{4}dp[1][n-2], &j=1 \\
&\frac{1}{4}dp[i+1][n-2] + \frac{1}{4}dp[1][1] + \frac{2}{4}dp[1][n-1], &j=2 \\
&\frac{1}{4}dp[i+1][n-3] + \frac{1}{4}dp[1][n-1] + \frac{1}{4}dp[1][1] + \frac{1}{4}dp[1][n], &j=3 \\
&\frac{1}{4}dp[i+1][n] + \frac{2}{4}dp[1][n] + \frac{1}{4}dp[1][1], &j=4 \\
&\frac{3}{4}dp[1][j-3] + \frac{1}{4}dp[i+1][j-3], &j>4
\end{aligned}
\right .
\]
因为找不到一个有效的常量，因此考虑解n*m元方程组。方法是高斯消元。
3. 代码
1 /* 4326 */ 2 #include <iostream> 3 #include <sstream> 4 #include <string> 5 #include <map> 6 #include <queue> 7 #include <set> 8 #include <stack> 9 #include <vector> 10 #include <deque> 11 #include <bitset> 12 #include <algorithm> 13 #include <cstdio> 14 #include <cmath> 15 #include <ctime> 16 #include <cstring> 17 #include <climits> 18 #include <cctype> 19 #include <cassert> 20 #include <functional> 21 #include <iterator> 22 #include <iomanip> 23 using namespace std; 24 //#pragma comment(linker,"/STACK:102400000,1024000") 25 26 #define sti set<int> 27 #define stpii set<pair<int, int> > 28 #define mpii map<int,int> 29 #define vi vector<int> 30 #define pii pair<int,int> 31 #define vpii vector<pair<int,int> > 32 #define rep(i, a, n) for (int i=a;i<n;++i) 33 #define per(i, a, n) for (int i=n-1;i>=a;--i) 34 #define clr clear 35 #define pb push_back 36 #define mp make_pair 37 #define fir first 38 #define sec second 39 #define all(x) (x).begin(),(x).end() 40 #define SZ(x) ((int)(x).size()) 41 #define lson l, mid, rt<<1 42 #define rson mid+1, r, rt<<1|1 43 44 const int maxn = 105; 45 const double eps = 1e-8; 46 typedef double mat[maxn][maxn]; 47 double x[maxn]; 48 mat g; 49 int n, m, k; 50 51 void gauss_elimination(mat& g, int n) { 52 int r; 53 54 rep(i, 0, n) { 55 r = i; 56 rep(j, i+1, n) { 57 if (fabs(g[j][i]) > fabs(g[r][i])) 58 r = j; 59 } 60 if (r != i) { 61 rep(j, 0, n+1) 62 swap(g[r][j], g[i][j]); 63 } 64 65 rep(k, i+1, n) { 66 if (fabs(g[i][i]) < eps) 67 continue; 68 double f = g[k][i] / g[i][i]; 69 rep(j, i, n+1) 70 g[k][j] -= f * g[i][j]; 71 } 72 } 73 74 per(i, 0, n) { 75 rep(j, i+1, n) 76 g[i][n] -= g[j][n] * g[i][j]; 77 g[i][n] /= g[i][i]; 78 } 79 } 80 81 void add(int ridx, int i, int j, double val) { 82 if (i == m) { 83 if (j == 1) 84 g[ridx][i*n+j-1] -= val; 85 return ; 86 } 87 88 g[ridx][i*n+j-1] += val; 89 } 90 91 void solve() { 92 int idx = 0; 93 94 memset(g, 0, sizeof(g)); 95 96 rep(i, 0, m) { 97 rep(j, 1, n+1) { 98 add(idx, i, j, 1.0); 99 if (j == 1) { 100 add(idx, i+1, j, -0.25); 101 add(idx, 1, n-2, -0.75); 102 } else if (j == 2) { 103 add(idx, i+1, n-2, -0.25); 104 add(idx, 1, 1, -0.25); 105 add(idx, 1, n-1, -0.5); 106 } else if (j == 3) { 107 add(idx, i+1, n-1, -0.25); 108 add(idx, 1, n-1, -0.25); 109 add(idx, 1, 1, -0.25); 110 add(idx, 1, n, -0.25); 111 } else if (j == 4) { 112 add(idx, i+1, n, -0.25); 113 add(idx, 1, n, -0.5); 114 add(idx, 1, 1, -0.25); 115 } else { 116 add(idx, 1, j-3, -0.75); 117 add(idx, i+1, j-3, -0.25); 118 } 119 ++idx; 120 } 121 } 122 123 gauss_elimination(g, idx); 124 double ans = g[k-1][idx]; 125 printf("%.6lf\n", ans); 126 } 127 128 int main() { 129 ios::sync_with_stdio(false); 130 #ifndef ONLINE_JUDGE 131 freopen("data.in", "r", stdin); 132 freopen("data.out", "w", stdout); 133 #endif 134 135 int t; 136 137 scanf("%d", &t); 138 rep(tt, 1, t+1) { 139 scanf("%d%d%d", &n, &m, &k); 140 printf("Case #%d: ", tt); 141 solve(); 142 } 143 144 #ifndef ONLINE_JUDGE 145 printf("time = %d.\n", (int)clock()); 146 #endif 147 148 return 0; 149 }