【題解】Codeforces GYM 102644A. Random Mood

#include <iostream>
#include <iomanip>
using namespace std;
 
int n;
double p, a[2][2], ans[2];
 
int main() {
    cin >> n >> p;
    ans[0] = 1;
    a[0][0] = 1-p;
    a[0][1] = p;
    a[1][0] = p;
    a[1][1] = 1-p;
    while (n){
        if (n & 1){
            double tmp[2] = {};
            for (int i = 0; i < 2; i++){
                for (int k = 0; k < 2; k++){
                    tmp[i] += a[i][k]*ans[k];
                }
            }
            for (int i = 0; i < 2; i++){
                ans[i] = tmp[i];
            }
        }
        double tmp[2][2] = {};
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 2; k++){
                    tmp[i][j] += a[i][k]*a[k][j];
                }
            }
        }
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                a[i][j] = tmp[i][j];
            }
        }
        n >>= 1;
    }
    cout << fixed << setprecision(9) << ans[0] << "\n";
}