小澳的坐标系

  首先我们可以想到简单的DP，f[i][0,1,2],表示第i步向上走、向左走、向右走的步数。向上走：f[i][0]=f[i-1][0]+f[i-1][1]+f[i-1][2],向左走、向右走：f[i][1]=f[i-1][0]+f[i-1][1]，f[i][2]=f[i-1][0]+f[i-1][2]。 这个显然可以用矩阵乘法优化: $\left[\begin{matrix}f_{(n-1,0)} & f_{(n-1,1)} & f_{(n-1,2)}\end{matrix}\right]\times\left[\begin{matrix}1 & 1 & 1 \\1 & 1 & 0 \\1 & 0 & 1\end{matrix}\right]=\left[\begin{matrix}f_{(n,0)} & f_{(n,1)} & f_{(n,2)}\end{matrix}\right]\ $ 于是我们就矩阵快速幂就行啦把单位矩阵乘n-2次即可 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; const int mod=1e9+7; int n; int a[4][4],f[4],bas[4][4],tmp[4][4]; void muti() { memset(tmp,0,sizeof(tmp)); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) for(int k=1;k<=3;k++) tmp[i][j]=(tmp[i][j]+a[i][k]*bas[k][j])%mod; memcpy(a,tmp,sizeof(a)); } void Muti() { memset(tmp,0,sizeof(tmp)); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) for(int k=1;k<=3;k++) tmp[i][j]=(tmp[i][j]+bas[i][k]*bas[k][j])%mod; memcpy(bas,tmp,sizeof(bas)); } void pow(int k) { if(k==0) return; if(k%2==1) muti(); Muti(); pow(k/2); } signed main() { scanf("%lld",&n); a[1][1]=a[1][2]=a[1][3]=a[2][1]=a[2][2]=a[3][1]=a[3][3]=1; memcpy(bas,a,sizeof(bas)); pow(n-2); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) f[i]=(f[i]+a[j][i])%mod; printf("%lld",(f[1]+f[2]+f[3])%mod); return 0; } ```