hdu-5667 Sequence(矩阵快速幂+费马小定理+快速幂)

时间：2021-07-12 15:30:34

题目链接：

Sequence

Time Limit: 2000/1000 MS (Java/Others)   

 Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Holion August will eat every thing he has found.

Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.

fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwise

He gives you 5 numbers n,a,b,c,p,and he will eat fn foods.But there are only p foods,so you should tell him fn mod p.

 
Input
 
The first line has a number,T,means testcase.

Each testcase has 5 numbers,including n,a,b,c,p in a line.

1≤T≤10,1≤n≤10^18,1≤a,b,c≤10^9,p is a prime number,and p≤10^9+7.

 
Output
 
Output one number for each case,which is fn mod p.
 
Sample Input
 
1
5 3 3 3 233
 
Sample Output
 
190
 
题意：
 
问f(n)对p取模的结果;
 
思路：
 
(ab)p[n]= ab * ((ab)p[n-1])c * ((ab)p[n-2]);递推式子可以这样写;
合并后变为(ab)p[n]=(ab)(c*p[n-1]+p[n-2]+1);
可以得到p[n]=c*p[n-1]+p[n-2]+1;
这样的递推式可以用矩阵乘法得到第n项;这是矩阵乘法的一个应用,给matrix67大神的博客地址可以学习,点这里
构造矩阵乘法:
 
p[n]　　　　c    1    1　　　　p[n-1]
p[n-1]   =  1   0    0   *  　p[n-2]
1　　　　　  0   0    1　　　　　　1
 
然后这中间还有一个问题,就是取模的问题;ab*p[n]%mod=ab*p[n]%(mod-1)%mod;
这是根据费马小定理得到的;a(p-1)Ξ1%p;这里给出地址
 
ab*p[n]%mod=ab*p[n]/(mod-1)*(mod-1)+b*p[n]%(mod-1)%mod;
 
令x=b*p[n]/(mod-1)则ab*p[n]%mod=ax*(mod-1)+b*p[n]%(mod-1)%mod=ab*p[n]%(mod-1)%mod;
这就是取模的结果啦;
然后就是快速幂算答案啦;
还有要注意的就是a%p==0的情况;
 
 
AC代码：
 
 
/*5667    0MS    1584K    1835B    G++    2014300227*/

#include <bits/stdc++.h>

using namespace std;

const int N=1e4+;

typedef long long ll;

const int mod=1e9+;

ll n,a,b,c,p;

struct matrix

{

    ll a[][];

};

matrix A;

void Iint(ll x)//矩阵初始化;

{

    A.a[][]=x;

    A.a[][]=;

    A.a[][]=;

    A.a[][]=;

    A.a[][]=A.a[][]=;

    A.a[][]=A.a[][]=;

    A.a[][]=;

}

matrix mul(matrix x,matrix y)//矩阵相乘

{

    matrix ans;

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

    {

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

        {

            ans.a[i][j]=;

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

            {

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

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

            }

        }

    }

    return ans;

}

ll fast_fun(matrix temp,ll num)//矩阵快速幂;

{

    matrix s,base;

    for(int i=;i<;i++)//s初始化为单位矩阵

    {

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

        {

            s.a[i][j]=;

            base.a[i][j]=temp.a[i][j];

        }

    }

    s.a[][]=s.a[][]=s.a[][]=;

    while(num)

    {

        if(num&)

        {

            s=mul(s,base);

        }

        base=mul(base,base);

        num=(num>>);

    }

    return (s.a[][]+s.a[][])%(p-);

}

ll fastpow(ll fx,ll fy)//快速幂求结果;

{

    ll s=,base=fx;

    while(fy)

    {

        if(fy&)

        {

            s*=base;

            s%=p;

        }

        base*=base;

        base%=p;

        fy=(fy>>);

    }

    return s;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

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

        Iint(c);

        if(n==)printf("1\n");

        else if(n==)printf("%lld\n",fastpow(a,b));

        else

        {

            if(a%p==)printf("0\n");

            else {

            ll gg=fast_fun(A,n-)*b%(p-);

            printf("%lld\n",fastpow(a,gg));

            }

        }

    }

    return ;

}
 

相关文章