Editorial for Matrix Exponentiation - Random Mood
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta gọi ~H_n~ là xác suất để tâm trạng Limak là vui sau ~n~ giây, ~S_n~ là xác suất để tâm trạng của Limak là buồn sau ~n~ giây. Ta có công thức truy hồi sau:
$$\begin{cases} H_1 = 1, S_1 = 0 \\ H_n = (1-p) \times H_{n-1} + p \times S_{n-1}\\ S_n = p \times H_{n-1} + (1-p) \times S_{n-1} \end{cases} (\forall n \geq 2)$$
~~
Công thức trên đúng vì sau mỗi giây, xác suất thay đổi trạng thái là ~p~ và không thay đổi trạng thái là ~1-p~.
Độ phức tạp của thuật toán quy hoạch động thông thường là ~O(n)~, nhưng với độ phức tạp này thì sẽ không thể qua được các giới hạn của bài. Ta có thể đạt được độ phức tạp ~O(log \: n)~ thông qua kĩ thuật nhân ma trận.
Code tham khảo
##include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i = 0; i < (n); i++) struct Matrix { double a[2][2] = {{0,0},{0,0}}; Matrix operator *(const Matrix& other) { Matrix product; REP(i,2)REP(j,2)REP(k,2) { product.a[i][k] += a[i][j] * other.a[j][k]; } return product; } }; Matrix expo_power(Matrix a, int k) { Matrix product; REP(i,2) product.a[i][i] = 1; while(k > 0) { if(k % 2) { product = product * a; } a = a * a; k /= 2; } return product; } int main() { // A. Random Mood int n; double p; cin >> n >> p; Matrix single; single.a[0][0] = 1 - p; single.a[0][1] = p; single.a[1][0] = p; single.a[1][1] = 1 - p; Matrix total = expo_power(single, n); cout << setprecision(10) << fixed << total.a[0][0] << endl; }
Comments