#include #include #include #include #include #include #include #include #include #include using namespace std; //マルコフなんちゃらの練習 //[n*p] * [p*m] => [n*m] template vector< vector > multmat(const vector > &A, const vector> &B, int n, int p, int m){ vector > C(n, vector(m,0)); for(int i=0; i vector< vector > mat_pow(vector > A, int k){ int n = A.size(); vector > ret(n, vector(n, 0) ); for(int i=0; i0){ if(k&1) ret = multmat(A,ret, n,n,n); A = multmat(A,A, n,n,n); k>>=1; } return ret; } void print_vec(const vector> &v){ #ifdef DBG_ for(auto l : v){ for(auto x : l){ cerr << x << "\t"; } cerr << endl; } cerr << endl; #endif } int main(){ double p,q; cin >> p >> q; //遷移図的な何か // aは表の状態、 bは裏の状態、 sははじめ、 tは終わり // s -> a (p) // -> b (1-p) // a -> t (q) // -> b (1-q) // b -> a (1) // t -> t (1) //遷移行列 vector> P(4, vector(4,0)); P = { // s a b t {0, p, 1-p, 0}, {0, 0, 1-q, q}, {0, 1, 0, 0}, {0, 0, 0, 1} // <- ここが吸収状態 }; print_vec(P); //初期状態 vector> S(1, vector(4,0)); S = { {1,0,0,0} }; print_vec(S); double p1, p2; auto P2 = mat_pow(P, 2); //0回ひっくり返す print_vec(P2); auto P3 = mat_pow(P, 3); //1回ひっくり返す print_vec(P3); auto P4 = mat_pow(P, 4); //2回ひっくり返す print_vec(P4); { auto tmp = multmat(S, P3, 1,4,4); auto tmp_ = multmat(S, P2, 1,4,4); print_vec(tmp); print_vec(tmp_); p1 = tmp[0][3] - tmp_[0][3]; } { auto tmp = multmat(S, P4, 1,4,4); auto tmp_ = multmat(S, P3, 1,4,4); print_vec(tmp); print_vec(tmp_); p2 = tmp[0][3] - tmp_[0][3]; } //cerr << p1 << " " << p2 << endl; cout << (p1