HDU 4549 Mフィボナッチ数列(行列べき乗)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4549
标题:F[0]=a,F[1]=b,F[n]=F[n-1]*F[n-2].
考え方:手で計算すると、最後にF[n]=a^x*b^yとなり、xとyは連続する2つのFibとなる.したがって,この2つの係数xとyを求めればよい.ここでA^x=A^(x%Phi(C)+Phi(C))(mod C)に注意してください.したがって,行列の高速べき乗を求める場合のモードの数はmod=1億007ではなくmod−1である.
 

struct matrix

{

    i64 a[2][2];



    void init(int x)

    {

        clr(a,0);

        if(x) a[0][0]=a[1][1]=1;

    }



    matrix operator*(matrix p)

    {

        matrix ans;

        ans.init(0);

        int i,j,k;

        FOR0(k,2) FOR0(i,2) FOR0(j,2)

        {

            ans.a[i][j]+=a[i][k]*p.a[k][j]%(mod-1);

            ans.a[i][j]%=(mod-1);

        }

        return ans;

    }



    matrix pow(int n)

    {

        matrix ans,p=*this;

        ans.init(1);

        while(n)

        {

            if(n&1) ans=ans*p;

            p=p*p;

            n>>=1;

        }

        return ans;

    }

};



matrix p;

int a,b,n;





i64 Pow(i64 a,i64 b)

{

    i64 ans=1;

    while(b)

    {

        if(b&1) ans=ans*a%mod;

        a=a*a%mod;

        b>>=1;

    }

    return ans;

}



int main()

{

    p.a[0][0]=p.a[1][0]=p.a[0][1]=1;

    p.a[1][1]=0;

    Rush(a)

    {

        RD(b,n);

        if(n==0) PR(a);

        else if(n==1) PR(b);

        else

        {

            matrix temp=p.pow(n-2);

            int x=(temp.a[0][1]+temp.a[1][1])%(mod-1);

            int y=(temp.a[0][0]+temp.a[1][0])%(mod-1);

            PR(Pow(a,x)*Pow(b,y)%mod);

        }

    }

}