[蓝桥杯训练系统] ALGO-199 奇异的虫群 (矩阵快速幂) Apare_xzc
程序员文章站
2022-04-06 21:01:20
...
[蓝桥杯训练系统] 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