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;
}