HDU 5667 Sequence 矩阵快速幂+费马小定理

题目不难懂。式子是一个递推式，并且不难发现f[n]都是a的整数次幂。(f[1]=a⁰;f[2]=a^b;f[3]=a^b*f[2]^c*f[1]...)

我们先只看指数部分，设h[n]. 则

h[1]=0;

h[2]=b;

h[3]=b+h[2]*c+h[1];

h[n]=b+h[n-1]*c+h[n-1].

h[n]式三个数之和的递推式，所以就可以转化为3x3的矩阵与3x1的矩阵相乘。于是

h[n]　　　　　 c 1 b　　　　h[n-1]

h[n-1]　　=　　1 0 0　　*　 h[n-2]　

1　　　　 0 0 1　　　　 1

又根据费马小定理(a^p-1%p=1,p是质数且a,p互质)可得：a^h[n]%mod=a^h[n]%(mod-1)%mod.

因为 a^h[n]%mod= a^{x*(mod-1)+h[n]%(mod-1)}%mod = a^x*(mod-1)*a^h[n]%(mod-1)%mod = a^h[n]%(mod-1)%mod;

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

ll p;

struct Mat

{

    ll mat[][];

};

Mat Multiply(Mat a, Mat b)

{

    Mat c;

    memset(c.mat, , sizeof(c.mat));

    for(int k = ; k < ; ++k)

        for(int i = ; i < ; ++i)

            if(a.mat[i][k])

                for(int j = ; j < ; ++j)

                    if(b.mat[k][j])

                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%(p-);

    return c;

}

Mat QuickPower(Mat a, ll k)

{

    Mat c;

    memset(c.mat,,sizeof(c.mat));

    for(int i = ; i <; ++i)

        c.mat[i][i]=;

    for(; k; k >>= )

    {

        if(k&) c = Multiply(c,a);

        a = Multiply(a,a);

    }

    return c;

}

ll Powermod(ll a,ll b)

{

    a%=p;

    ll ans=;

    for(; b; b>>=)

    {

        if(b&) ans=(ans*a)%p;

        a=(a*a)%p;

    }

    return ans;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int T;

    scanf("%d",&T);

    ll n,a,b,c;

    Mat x;

    while(T--)

    {

        scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&p);

        if(n==)

            printf("1\n");

        else if(n==)

            printf("%I64d\n",Powermod(a,b));

        else

        {

            x.mat[][]=c; x.mat[][]=; x.mat[][]=b;

            x.mat[][]=; x.mat[][]=; x.mat[][]=;

            x.mat[][]=; x.mat[][]=; x.mat[][]=;

            x=QuickPower(x,n-);

            ll k=(x.mat[][]*b+x.mat[][]);

            printf("%I64d\n",Powermod(a,k));

        }

    }

    return ;

}

巴特西

HDU 5667 Sequence 矩阵快速幂+费马小定理

最新文章

热门文章