[蓝桥杯训练系统] ALGO-199 奇异的虫群 (矩阵快速幂) Apare_xzc

[蓝桥杯训练系统] ALGO-199 奇异的虫群 (矩阵快速幂) Apare_xzc



题面:


分析:

就是求斐波那契数列第n项

可用矩阵快速幂

A1 = 1   B1 = 1
A2 = 2   B2 = 1
A3 = 3   B3=  2
A4 = 5   B4 = 3
A5 = 8   B5 = 5
...
A[i+1] = A[i]+B[i]
B[i+1] = A[i]

矩阵递推式如下:

| A[i+1]  |        =      |1  1|     *      |  A[i]  |
| B[i+1]  |               |1  0|            |  B[i]  |

我的AC代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5;
const int mod = 1000000007;
LL arr[N][N];
void Mul(LL a[N][N],LL b[N][N],int n) /// a(n,n) = a(n,n) * b(n,n)
{
	LL c[N][N] = {0};
	for(int row=0; row<n; ++row)
		for(int col=0; col<n; ++col)
			for(int k=0;k<n;++k)
				c[row][col] = (a[row][k]*b[k][col]%mod+c[row][col])%mod;
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			a[i][j] = c[i][j];
} 
void solve(LL a[N][N],int n,LL m)
{
	LL ans[N][N] = {0};
	for(int i=0; i<n; ++i) ans[i][i] = 1;
	while(m>0)
	{
		if(m&1) Mul(ans,a,n);
		Mul(a,a,n);
		m >>= 1;
	}
	printf("%lld\n",ans[0][0]); 
}
int main()
{
	LL m;
	while(cin>>m)
	{
		arr[0][0] = arr[0][1] = arr[1][0] = 1;
		arr[1][1] = 0;
		solve(arr,2,m);
	}
	return 0;
}


矩阵快速幂入门水题
xzc
2020.1.13 16:09


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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