POJ3744Scout YYF I(求概率 + 矩阵快速幂)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct Mat
{
    double mat[3][3];
};
int x[30],n;
Mat operator*(Mat a,Mat b)
{
    Mat c;
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
            c.mat[i][j] = 0;
    }
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 2; k++)
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
        }
    }
    return c;
}
Mat operator^(Mat a, int k)
{
    Mat c;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            c.mat[i][j] = (i == j);
    while(k)
    {
        if(k % 2)
            c = c * a;
        a = a * a;
        k = k / 2;
    }
    return c;
}
int main()
{
    double p;
    while(scanf("%d%lf", &n,&p) != EOF)
    {
        for(int i = 0; i < n; i++)
            scanf("%d", &x[i]);
        sort(x, x + n);
        Mat tt,temp;
        temp.mat[0][0] = tt.mat[0][0] = p;
        temp.mat[0][1] = tt.mat[0][1] = 1 - p;
        temp.mat[1][0] = tt.mat[1][0] = 1;
        temp.mat[1][1] = tt.mat[1][1] = 0;

        temp = tt ^ (x[0] - 1);
        double ans = 1;
        ans *= (1 - temp.mat[0][0]);
        for(int i = 1; i < n; i++)
        {
            if(x[i] == x[i - 1])
                continue;
            temp = tt ^ (x[i] - x[i - 1] - 1); // 因为要从x[i - 1] + 1开始走，x[i - 1] 是雷
            ans *= (1 - temp.mat[0][0]);
        }
        printf("%0.7lf\n", ans);
    }
    return 0;
}