矩阵快速幂模版

博主链接

矩阵快速幂模版

#include<bits/stdc++.h> 
using namespace std;
int N=7;
void Matrix(int (&a)[2][2],int b[2][2]){
	int tmp[2][2]={0};
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%N;
	for(int i=0;i<2;++i){
				for(int j=0;j<2;++j){
			a[i][j]=tmp[i][j];
	    }
	}
}
int main(){
	int a,b,n;
	while(scanf("%d%d%d",&a,&b,&n)){
		if(a==0&&b==0&&n==0)break;
		if(n==1){
           cout<<1<<endl;
           continue;
       		}
		int temp[2][2]={a,b,0,0},cot[2][2]={1,0,0,1}, x[2] = {1, 1};
		n-=2;
		while(n){ 
			if(n&1)Matrix(cot,temp);
			Matrix(temp,temp);
			n/=2;

		}
		int ans=0;
		for(int i=0;i<2;i++)
		ans=(ans+x[i]*cot[0][i])%N;
		cout<<ans<<endl;
	}
} 

快速幂函数

ll quick_mod(ll a,ll b,ll c) //快速幂计算(a^b)%c
{
    ll ans = 1;
    while(b)
    {
        if(b&1)   //相当于b%2==1
            ans = (ans*a)%c;
        a = (a*a)%c;
        b>>=1;    //相当于b/=2
    }
    return ans;
}

 

全部评论

相关推荐

05-07 19:10
已编辑
中国科学技术大学 C++
silly01:现在先去 momenta,8-9月去鹅找日常实习,八股文算法背好了你这随便进。不过建议补充一下后端知识,MySQL、Redis看下八股,再补个6824,加点go后台的技术栈,9月随便进大厂。CPP后端只能来WXG
点赞 评论 收藏
分享
迟缓的斜杠青年巴比Q...:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务