codeforce Gym 100425E The Street Escalator（期望，线性递推）

算数学期望，每个人都可以分开来考虑。X_i表示第i个人跑到另外一边的次数。

X_i服从二项分布。概率的和是个二项式，(p+1-p)^T，把二项式展开，p的偶次项是留在原来那一边的概率。

可以用((a+b)^T+(a-b)^T)/2来算出偶次项之和。

也可以用矩阵快速幂。矩阵构造如下

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cmath>

//#include<bits/stdc++.h>

using namespace std;

typedef double MType;

const int maxn = 1e5+;

struct Person

{

    double p;

    char side;

    int T;

    void IN(){

        scanf("%d %c %lf",&T,&side,&p);

    }

    void cal(MType &lft, MType &rgh){

        double keep = (+pow(-*p,T))/;

        if(side == 'L') lft = keep, rgh = -keep;

        else lft = -keep, rgh = keep;

    }

}P;

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int N; scanf("%d",&N);

    MType L = , R = , ans = ;

    for(int i = ; i < N; i++){

        P.IN();

        MType l,r;

        P.cal(l,r);

        ans += L*l + R*r;

        L = r;

        R = l;

    }

    printf("%.12lf",ans);

    return ;

}

快速幂

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cmath>

//#include<bits/stdc++.h>

using namespace std;

const int MSIZE = , n = ;

typedef double MType;

struct Matrix

{

    MType dat[MSIZE][MSIZE];

    MType *operator [](int x){ return dat[x]; }

    Matrix operator * (Matrix& B) {

        Matrix re;

        for(int i = ; i < n; i++){

            for(int j = ; j < n; j++){

                re[i][j] = ;

                for(int k = ; k < n; k++){

                    re[i][j] += dat[i][k]*B[k][j];

                }

            }

        }

        return re;

    }

    Matrix operator ^ (int q){

        Matrix Re, A = *this;

        for(int i = ; i < n; i++){

            for(int j = ; j < n; j++){

                Re[i][j] = i == j?:;

            }

        }

        while(q){

            if(q&){

                Re = Re * A;

            }

            A = A * A;

            q >>= ;

        }

        return Re;

    }

};

const int maxn = 1e5+;

struct Person

{

    double p;

    char side;

    int T;

    void IN(){

        scanf("%d %c %lf",&T,&side,&p);

    }

    void cal(MType &lft, MType &rgh){

        Matrix C;

        C[][] = C[][] = -p;

        C[][] = C[][] = p;

        C = C^T;

        if(side == 'L') lft = C[][], rgh = C[][];

        else lft = C[][], rgh = C[][];

    }

}P[maxn];

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int N; scanf("%d",&N);

    for(int i = ; i < N; i++){

        P[i].IN();

    }

    //sort(P,P+N);

    MType L = , R = , ans = ;

    for(int i = ; i < N; i++){

        MType l,r;

        P[i].cal(l,r);

        ans += L*l + R*r;

        L = r;

        R = l;

    }

    printf("%.12lf",ans);

    return ;

}

巴特西

codeforce Gym 100425E The Street Escalator（期望，线性递推）

最新文章

热门文章