不知道大家做没做过传球游戏，这一题和传球游戏的转移方程几乎一样。
令(A)为(1)点，(E)为(5)点，那么(f[i][j])代表第i步走到j的方案数。
[f[i][j]=f[i−1][j+1]+f[i−1][j−1]
]
因为题中给的是一个环，所以有几种情况。
[if(j==8)~f[i][j]=f[i−1][1]+f[i−1][7]
]
[if(j==1)~f[i][j]=f[i−1][8]+f[i−1][2]
]
还有，因为题中说，到了(E)点，就不会再动了。
[if(j==4)~f[i][j]=f[i−1][3]
]
[if(j==6)~f[i][j]=f[i−1][7]
]
边界很显然(f[0][1]=1)。但是我们注意这一题(n≤10^7)，所以我们要滚动数组。
实际上我分析了一波，应该要用矩阵快速幂优化掉(n)那一维的，但是我交了一份递推代码上去也(A)了。
那么就不用管了，上代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int f[2][9]={},n,t=0;
cin>>n;
f[t][1]=1;
for (int i=1;i<=n;++i) {
t=!t;
for (int j=1;j<=8;++j) {
if (j==1) f[t][j]=f[!t][8]+f[!t][j+1];
else if (j==8) f[t][j]=f[!t][j-1]+f[!t][1];
else if (j==4) f[t][j]=f[!t][j-1];
else if (j==6) f[t][j]=f[!t][j+1];
else f[t][j]=f[!t][j-1]+f[!t][j+1];
f[t][j]%=1000;
}
}
cout<<f[t][5];
return 0;
}