AcWing 205. 斐波那契
原题链接
中等
作者:
凯濛
,
2024-04-08 13:09:28
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
const int MOD=10000;
void mul(int a[][2],int b[][2])
{
int c[2][2]={0};
memset(c,0,sizeof c);
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j]) % MOD;
memcpy(a, c, sizeof c);
}
int fib(int n)
{
int a[2][2]={0,1,0,0};
int f[2][2]={0,1,1,1};
while(n)
{
if(n & 1) mul(a, f);
mul(f, f);
n >>= 1;
}
return a[0][0];
}
int main()
{
int n;
while(cin >> n, n != -1)
cout << fib(n) << endl;
return 0;
}