代码拉取完成,页面将自动刷新
#include <algorithm>/*{{{*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
namespace RA {
int r(int p) { return 1ll * rand() * rand() % p; }
int r(int L, int R) { return r(R - L + 1) + L; }
} // namespace RA
/******************heading******************/
const int N = 105;
const double eps = 1e-11;
class TorusSailing {
public:
double f[N][N][N * 2], *g[N * 2], h[N][N];
int lg = 0;
double expectedTime(int n, int m, int goalX, int goalY) {
FOR(i, 1, m) f[n][i][i] = 1;
FOR(i, 1, n - 1) f[i][m][m + i] = 1;
ROF(i, n - 1, 1) ROF(j, m - 1, 1) {
FOR(k, 0, n + m) f[i][j][k] = (f[i + 1][j][k] + f[i][j + 1][k]) / 2;
f[i][j][0] += 1; //常数
}
FOR(i, 1, m - 1) { // f[n][i]
FOR(k, 0, n + m)
f[n][i][k] = (f[1][i][k] + f[n][i == m ? 1 : i + 1][k]) / 2;
f[n][i][0] += 1;
f[n][i][i] -= 1;
}
FOR(i, 1, n - 1) { // f[i][m]
FOR(k, 0, n + m) f[i][m][k] = (f[i + 1][m][k] + f[i][1][k]) / 2;
f[i][m][0] += 1;
f[i][m][m + i] -= 1;
}
FOR(i, 1, m) g[++lg] = f[n][i], g[lg][0] = -g[lg][0];
FOR(i, 1, n - 1) g[++lg] = f[i][m], g[lg][0] = -g[lg][0];
assert(lg == n + m - 1);
// Gauss
FOR(i, 1, lg) {
FOR(j, i, lg) if (abs(g[j][i]) > eps) {
FOR(k, 0, lg) swap(g[i][k], g[j][k]);
break;
}
assert(abs(g[i][i]) > eps);
FOR(j, 1, lg) {
if (i == j) continue;
double r = g[j][i] / g[i][i];
FOR(k, i, lg) g[j][k] -= g[i][k] * r;
g[j][0] -= g[i][0] * r;
}
}
FOR(i, 1, lg) g[i][0] /= g[i][i], g[i][i] /= g[i][i];
FOR(i, 1, m) h[n][i] = g[i][0];
FOR(i, 1, n - 1) h[i][m] = g[i + m][0];
ROF(i, n - 1, 1) ROF(j, m - 1, 1) {
h[i][j] = (h[i + 1][j] + h[i][j + 1]) / 2 + 1;
}
return h[n - goalX][m - goalY];
}
};
TorusSailing test;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << test.expectedTime(a, b, c, d) << endl;
return 0;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。