Hdu 4549 M斐波那契数列 (矩阵费马小定理降幂)

怼烎@ 2022-09-17 12:19 125阅读 0赞

费马小定理：[费马小定理 - 维基百科，自由的百科全书][-]

思路：利用费马小定理推导的降幂公式

![SouthEast][]

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define i64 __int64
    
    const i64 mod=1000000007;
    const i64 modd=mod-1;
    const int N=2;
    
    class Matrix
    {
    public:
    	i64 a[N][N];
    	int n;   //矩阵大小
    
    	void init (int x)
    	{
    		memset(a,0,sizeof(a));
    		if (x) for (int i=0;i<N;i++)
    			a[i][i]=1;
        }
    
    	Matrix operator * (Matrix b)
    	{
    		Matrix p;
    		p.n=b.n;   //
    		p.init(0);
    		for (int i=0;i<n;i++) for (int j=0;j<n;j++)
    			for (int k=0;k<n;k++)
    				(p.a[i][j]+=a[i][k]*b.a[k][j]%modd)%=modd;
    		return p;
    	}
    
    	Matrix power (int t)
    	{
    		Matrix ans,p=*this;
    		ans.n=p.n;  //
    		ans.init(1);
    		while (t)
    		{
    			if (t&1) ans=ans*p;
    			p=p*p;
    			t>>=1;
    		}
    		return ans;
    	}
    }a;
    
    __int64 modPow (__int64 s,__int64 index,__int64 mod)
    //蒙哥马利幂模算法  
    //快速幂  
    //返回值(s^index)%mod  
    {    
        __int64 ans=1;    
        s%=mod;    
        while (index>=1)    
        {    
            if ((index&1)==1)   //奇数    
                ans=(ans*s)%mod;    
            index>>=1;    
            s=s*s%mod;    
        }    
        return ans;    
    }  
    
    void Deal (int n)
    {//注意矩阵快速幂的模用的是modd,即mod-1;
    	a.init(0);
    	a.n=2;
    	a.a[0][0]=1,a.a[0][1]=1;
    	a.a[1][0]=1,a.a[1][1]=0;
    	a=a.power(n-2);
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	i64 k,t,n;
    	while (~scanf("%I64d%I64d%I64d",&k,&t,&n))
    	{
    		if (n==0)
    		{
    			printf("%I64d\n",k%mod);
    			continue;
    		}
    		else if (n==1)
    		{
    			printf("%I64d\n",t%mod);
    			continue;
    		}
    		else if (n==2)
    		{
    			printf("%I64d\n",k*t%mod);
    			continue;
    		}
    		else
    		{
    			Deal (n);
    			i64 index1=(a.a[1][0]+a.a[1][1])%(mod-1);  //a的次数
    			i64 index2=(a.a[0][0]+a.a[0][1])%(mod-1);  //b的次数
    			i64 res=modPow(k,index1,mod);
    			res=(res*modPow(t,index2,mod))%mod;
    			printf("%I64d\n",res);
    		}
    		
    	}
    	return 0;
    }

[-]: http://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86
[SouthEast]: /images/20220828/b86fa0456e2f47f8b59c9c853119c013.png