cf696 C. PLEASE（矩阵快速幂、欧拉定理）

题意：

三个盒子排成一排，初始有一个钥匙在中间的盒子里。每次随机选两个相邻盒子交换位置，问n次操作后钥匙在中间的概率。

给定m个整数 \(a_i\)，n是它们的积。以最简分数的形式输出答案，对1e9+7取模。

\(m\le 1e5, 1\le a_i\le 1e18\)

思路：

n=0，答案是1；n=1，答案是0。发现第一步把钥匙换到边上，后面的某第 \(k\) 步把它换回来就能转移到 \(p(n-k)\) 。不难得到递推式 \(p_n=(p_{n-1}+p_{n-2})/2\)

设 \(f,g\) 分别为分子和分母，则 \(f_n=2f_{n-2}+f_{n-1},g_n=2g_{n-1}\)，那么分子永远为奇数，分母永远为偶数，所以过程中的每一步都是最简分数。

观察发现还可以写成 \(f_n=g_{n-1}-f_{n-1}\)，这样就能写出矩阵递推式

（实际上还有其他形式的式子，比如 \(p_n=(1-p_{n-1})/2\)）

然而指数超级大，直接做快速幂会超时！注意到模数是质数，可以用欧拉定理的推论 \(a^b\equiv a^{b \mod \phi(p)} \pmod p\)

int main()
{
    int m; cin >> m; while(m--)
    {
        ll x; cin >> x; x %= (mod-1);
        n = n * x % (mod-1);
    }
    n--; if(n < 0) n += mod-1;
    
    b[2][1] = 1;
    A[1][1] = -1, A[1][2] = 1, A[2][1] = 0, A[2][2] = 2;

    qmi(A, n), mul(A, b);
    cout << A[1][1] << '/' << A[2][1];
}