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