一句话题意
一个大小为8的环，求从1到5正好n步的方案数（途中不能经过5）。
Solution
巨说这个题目很水
应该是比较容易的DP，直接从把左边和右边的方案数加起来即可，但是有几个需要注意的地方：
1.因为n有1e7所以需要滚动数组。
2.因为不能经过5，所以4只能从3转移，6只能从7转移。
3.记得取模。
Coding
#include<bits/stdc++.h>
using namespace std;
int f[2][9];
const int P=1e3;
int main()
{
int n;
bool cnt=0;
cin>>n;
f[0][1]=1;
for(int i=1;i<=n;i++)
{
bool now=!cnt;
for(int j=1;j<=8;j++)
{
if(j==1) f[now][j]=f[cnt][8]+f[cnt][2];
else if(j==8) f[now][j]=f[cnt][1]+f[cnt][7];
else if(j==4) f[now][j]=f[cnt][3];
else if(j==6) f[now][j]=f[cnt][7];
else f[now][j]=f[cnt][j-1]+f[cnt][j+1];
f[now][j]%=P;
}
cnt=now;
}
cout<<f[cnt][5]%P;
return 0;
}原文：https://www.cnblogs.com/Le-mon/p/9607263.html