牛客等级之题N2(8.13场)A 斐波那契(矩阵快速幂)
程序员文章站
2024-03-17 21:30:34
...
传送门
题意:
思路:
斐波那契数列
用矩阵快速幂求斐波那契的第n项和第n+1项即可
代码:
const int N=2;//矩阵大小
ll quick(ll a,ll b){//快速幂
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b/=2;
}
return ans%mod;
}
struct sa
{
ll m[N][N];
};
sa Mul(sa a,sa b)//矩阵乘法
{
sa c;
memset(c.m,0, sizeof(c.m));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
return c;
}
sa quickjz(sa a,ll n)//矩阵快速幂
{
sa res;
memset(res.m,0, sizeof(res.m));
//res.m[0][0]=1;
//res.m[1][1]=1;
for(int i=0;i<N;i++)res.m[i][i]=1;
while(n)
{
if(n&1)
res=Mul(res,a);
n/=2;
a=Mul(a,a);
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
sa cnt={1,1,1,0};
ll n;
while(cin>>n){
sa a=quickjz(cnt,n);
ll p=a.m[1][0];
a=quickjz(cnt,n+1);
p=(p*a.m[1][0])%mod;
cout<<p<<endl;
}
return 0;
}