首页 > 其他 > 详细

CF 24 D. Broken robot

时间:2019-03-17 21:52:59      阅读:143      评论:0      收藏:0      [点我收藏+]

D. Broken robot

链接

分析:

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==-)f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-0;return x*f;
}

const int mod = 998244353, N = 1005;
const double f31 = 1.0 / 3.0, f32 = 2.0 / 3.0, f41 = 1.0 / 4.0, f43 = 3.0 / 4.0, f38 = 8.0 / 3.0, f23 = 3.0 / 2.0;

double dp[N][N], a[N][N];
int n, m, x, y; 

int ksm(int a,int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

void Make(int i) {
    a[1][1] = f32;
    a[1][2] = -f31;
    a[1][m + 1] = f31 * dp[i + 1][1] + 1;
    a[m][m - 1] = -f31;
    a[m][m] = f32;
    a[m][m + 1] = f31 * dp[i + 1][m] + 1;
    for (int j = 2; j < m; ++j) {
        a[j][j - 1] = -f41;
        a[j][j + 1] = -f41;
        a[j][j] = f43;
        a[j][m + 1] = f41 * dp[i + 1][j] + 1;
    }
}
void pr(int l,int r) {
    for (int i = l; i <= r; ++i) {
        for (int j = 1; j <= m + 1; ++j)
            printf("% .2lf ", a[i][j]);
        puts("");
    }
    puts("");
}
void solve(int i) {
    a[1][1] = 1; a[1][2] *= f23; a[1][m + 1] *= f23;
    for (int j = 2; j < m; ++j) {
        a[j][j - 1] = 0;
        a[j][j + 1] /= (a[j][j] + f41 * a[j - 1][j]);
        a[j][m + 1] += f41 * a[j - 1][m + 1];
        a[j][m + 1] /= (a[j][j] + f41 * a[j - 1][j]);
        a[j][j] = 1;
    }
    a[m][m - 1] = 0;
    a[m][m + 1] += (f31 * a[m - 1][m + 1]);
    a[m][m + 1] /= (a[m][m] + f31 * a[m - 1][m]);
    a[m][m] = 1;

    dp[i][m] = a[m][m + 1];
    for (int j = m - 1; j >= 1; --j) 
        dp[i][j] = a[j][m + 1] - a[j][j + 1] * dp[i][j + 1];
}
int main() {
    n = read(), m = read(), x = read(), y = read();
    if (m == 1) {
        printf("%.10lf", 2.0 * (n - x)); return 0;
    }
    for (int i = n - 1; i >= x; --i) {
        Make(i);
        solve(i);
    }
    printf("%.10lf", dp[x][y]);
    return 0;
}

 

CF 24 D. Broken robot

原文:https://www.cnblogs.com/mjtcn/p/10549120.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!