矩阵快速幂+扩展欧拉定理

对于一个矩阵\(A\)，我们有\(A^n \equiv A^{n\% \phi(m)+\phi(m)}(\%m)\)

经过简单的列举或推导可得

设目前进行了\(x\)轮，\(f(x)\)为分子，\(g(x)\)为分母

则有\(f(x)=g(x-1)-f(x-1),g(x)=2g(x-1)\)

由此及首项可得\(x>1\)时概率的分子一直是奇数，分母一直为2的幂

而\(x=1\)时分子为0，分母为1

即分子与分母恒互质

由此可得转移矩阵

\[A=\begin{bmatrix} -1 & 1 \\ 0 & 2 \end{bmatrix}\]

初始矩阵

\[B=\begin{bmatrix} 0 \\ 1 \end{bmatrix}\]

设

\(A^{n-1} \times B=\begin{bmatrix} p \\ q \end{bmatrix}\)

则p/q为所求

该算法时间复杂度为\(\Theta(k)\)，是本题的理论时间复杂度下限。

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MOD=1e9+7;const int siz=5;int n;long long v=1;struct Matrix{    long long v[siz][siz];    int x,y;    void clear(){memset(v,0,sizeof(v));x=y=0;}    void Mmul(Matrix a,Matrix b)    {        clear();        x=a.x,y=b.y;int c=a.y;        for(int i=1;i<=x;++i){            for(int j=1;j<=y;++j){                for(int k=1;k<=c;++k){                    v[i][j]+=a.v[i][k]*b.v[k][j]%MOD;                    v[i][j]=(v[i][j]%MOD+MOD)%MOD;                }            }        }return;    }    Matrix Mpw(Matrix a,long long b)    {        Matrix x;x.clear();x.x=x.y=a.x;        for(int i=1;i<=a.x;++i) x.v[i][i]=1;        while(b){            if(b&1) x.Mmul(x,a);            b>>=1;a.Mmul(a,a);        }return x;    }        void write()    {        for(int i=1;i<=x;++i){            for(int j=1;j<=y;++j){                printf("%lld ",v[i][j]);            }puts("");        }puts("");        return;    }}A,B;int main(){    scanf("%d",&n);    for(int i=1;i<=n;++i){long long x;scanf("%lld",&x);v=(x%(MOD-1)*v)%(MOD-1);}    v+=MOD-1;    A.x=A.y=2;B.x=2,B.y=1;    A.v[1][1]=-1,A.v[1][2]=1,A.v[2][2]=2;    B.v[2][1]=1;    A=A.Mpw(A,v-1);B.Mmul(A,B);    printf("%lld/%lld\n",B.v[1][1],B.v[2][1]);    return 0;}