Problem A: Apple(高斯消元)

• 可以发现具有非常多的方程， 然后高斯消元就能85分
• 然而我们发现这些方程组成了一些环， 我们仅仅设出一部分变量即可获得N个方程， 就可以A了
• trick 合并方程

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#include <cmath>
#define ldb long double
#define ll long long
#define mmp make_pair
#define M 222
using namespace std;
int read() {
	int nm = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
	return nm * f;
}
int n, m, x, y;

int id[M][M], cnt;
double d[M][M];
double f[M][M][M];
void gauss() {
	for(int i = 0; i <= cnt; i++) {
		int k = i;
		for(int j = i + 1; j <= cnt; j++) if(fabs(d[j][i]) > fabs(d[k][i])) k = j;
		if(k != i) for(int j = 0; j <= cnt + 1; j++) swap(d[i][j], d[k][j]);
		for(int j = 0; j <= cnt; j++) {
			if(i == j) continue;
			double t = d[j][i] / d[i][i];
			for(int k = 0; k <= cnt + 1; k++) d[j][k] -= d[i][k] * t;
		}
	}
}
int main() {
	n = read(), m = read(), x = read(), y = read();
	for(int i = 0; i < m; i++) f[n][i][i] = 1;
	for(int i = n - 1; i > x; i--) {
		double d = 0.5;
		for(int j = 0; j < m; j++,d *= 0.5)
			for(int k = 0; k <= m; k++)
				f[i][0][k] += d * f[i + 1][j][k];
		d *= 2;
		f[i][0][m] += 2.0 - d * 2.0;
		for(int k = 0; k <= m; k++)
			f[i][m][k] = (f[i][0][k] *= 1.0 / (1.0 - d));
		for(int j = m - 1; j > 0; j-- ) {
			for(int k = 0; k <= m; k++)
				f[i][j][k] += 0.5 * (f[i][j + 1][k] + f[i + 1][j][k]);
			f[i][j][m] += 1.0;
		}
	}
	for(int i = y - 1; i >= 0; i--) {
		for(int k = 0; k <= m; k++)
			f[x][i][k] += 0.5 * (f[x][i + 1][k] + f[x + 1][i][k]);
		f[x][i][m] += 1.0;
	}
	for(int k = 0; k <= m; k++)
		f[x][m][k] = f[x][0][k];
	for(int i = m - 1; i>y; i--) {
		for(int k = 0; k <= m; k++)
			f[x][i][k] += 0.5 * (f[x][i + 1][k] + f[x + 1][i][k]);
		f[x][i][m] += 1.0;
	}
	for(int i = x - 1; i >= 0; i--) {
		double d = 0.5;
		for(int j = 0; j < m; j++,d *= 0.5)
			for(int k = 0; k <= m; k++)
				f[i][0][k] += d * f[i + 1][j][k];
		d *= 2;
		f[i][0][m] += 2.0 - d * 2.0;
		for(int k = 0; k <= m; k++)
			f[i][m][k] = (f[i][0][k] *= 1.0 / (1.0 - d));
		for(int j = m - 1; j > 0; j--) {
			for(int k = 0; k <= m; k++)
				f[i][j][k] += 0.5 * (f[i][j + 1][k] + f[i + 1][j][k]);
			f[i][j][m] += 1.0;
		}
	}
	memcpy(d,f[0],sizeof(d));
	cnt = m - 1;
	for(int k = 0; k < m; k++) 	d[k][k] -= 1.0;
	gauss();
	printf("%.6lf
",-d[0][m]/d[0][0]);
	return 0;
}