欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-06 21:01:20
...

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


[蓝桥杯训练系统] 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;
}

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


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


相关标签: Apare_xzc 蓝桥杯