2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL P=1e9+7; struct node { LL a[3][3]; node(){memset(a,0,sizeof a);} }; node operator*(node A,node B) { node C; for (int i=1;i<=2;i++) for (int j=1;j<=2;j++) for (int k=1;k<=2;k++) C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P; return C; } node qpow(node A,LL b) { node C;for(int i=1;i<=2;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=C*A; A=A*A; } return C; } int main() { LL K;scanf("%lld",&K); node A;//A的第一行（f0,f1) A.a[1][1]=0;A.a[1][2]=1; node ff; ff.a[1][1]=0; ff.a[2][1]=1; ff.a[1][2]=1; ff.a[2][2]=1; A=A*qpow(ff,K); printf("%lld\n",A.a[1][1]); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:52:25
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL P=1e9+7; struct node { LL a[3][3]; node(){memset(a,0,sizeof a);} }; node operator*(node A,node B) { node C; for (int i=1;i<=2;i++) for (int j=1;j<=2;j++) for (int k=1;k<=2;k++) C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P; return C; } node qpow(node A,LL b) { node C;for(int i=1;i<=2;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=C*A; A=A*A; } return C; } int main() { LL K;scanf("%lld",&K); node A;//A的第一行（f0,f1) A.a[1][1]=0;A.a[1][2]=1; node ff; ff.a[1][1]=0; ff.a[2][1]=1; ff.a[1][2]=1; ff.a[2][2]=1; A=A*qpow(ff,K); printf("%lld\n",A.a[1][1]); return 0; }
- 1