矩阵快速幂做斐波那契数列

最新推荐文章于 2024-08-02 08:48:34 发布

WibleL

最新推荐文章于 2024-08-02 08:48:34 发布

阅读量188

点赞数

分类专栏：数论

本文链接：https://blog.csdn.net/speroc/article/details/107188631

版权

数论专栏收录该内容

2 篇文章

订阅专栏

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod = 10000;
int n;
struct mat{                                           
 long long a[5][5];
};
mat operator *(mat x,mat y)
{                 
 mat ans;
 memset(ans.a,0,sizeof(ans.a));
 for(int i = 1;i <= 2;i ++)
  for(int j = 1;j <= 2;j ++)
   for(int k = 1;k <= 2;k ++)
   ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
 return ans;
}
mat qsortmod(mat x,int k)
{                   
 mat s;
 memset(s.a,0,sizeof(s.a));
 for(int i = 1;i <= 2;i ++) s.a[i][i] = 1;
 while(k)
 {
  if(k & 1) s = s * x;
  k >>= 1;
  x = x * x; 
 }
 return s;
}
int main()
{
 mat tmp;
 tmp.a[1][1] = tmp.a[1][2] = tmp.a[2][1] = 1;
 tmp.a[2][2] = 0;
 while(~(scanf("%d",&n)) && n != -1)
 {
  if(n == 0) printf("0\n");
  else 
  {
   mat ans = qsortmod(tmp,n);
   printf("%d\n",ans.a[2][1]);
  }
 }
 return 0;
}