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. 代码
/* 4326 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
const double eps = 1e-;
typedef double mat[maxn][maxn];
double x[maxn];
mat g;
int n, m, k; void gauss_elimination(mat& g, int n) {
int r; rep(i, , n) {
r = i;
rep(j, i+, n) {
if (fabs(g[j][i]) > fabs(g[r][i]))
r = j;
}
if (r != i) {
rep(j, , n+)
swap(g[r][j], g[i][j]);
} rep(k, i+, n) {
if (fabs(g[i][i]) < eps)
continue;
double f = g[k][i] / g[i][i];
rep(j, i, n+)
g[k][j] -= f * g[i][j];
}
} per(i, , n) {
rep(j, i+, n)
g[i][n] -= g[j][n] * g[i][j];
g[i][n] /= g[i][i];
}
} void add(int ridx, int i, int j, double val) {
if (i == m) {
if (j == )
g[ridx][i*n+j-] -= val;
return ;
} g[ridx][i*n+j-] += val;
} void solve() {
int idx = ; memset(g, , sizeof(g)); rep(i, , m) {
rep(j, , n+) {
add(idx, i, j, 1.0);
if (j == ) {
add(idx, i+, j, -0.25);
add(idx, , n-, -0.75);
} else if (j == ) {
add(idx, i+, n-, -0.25);
add(idx, , , -0.25);
add(idx, , n-, -0.5);
} else if (j == ) {
add(idx, i+, n-, -0.25);
add(idx, , n-, -0.25);
add(idx, , , -0.25);
add(idx, , n, -0.25);
} else if (j == ) {
add(idx, i+, n, -0.25);
add(idx, , n, -0.5);
add(idx, , , -0.25);
} else {
add(idx, , j-, -0.75);
add(idx, i+, j-, -0.25);
}
++idx;
}
} gauss_elimination(g, idx);
double ans = g[k-][idx];
printf("%.6lf\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t; scanf("%d", &t);
rep(tt, , t+) {
scanf("%d%d%d", &n, &m, &k);
printf("Case #%d: ", tt);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}