题解：

首先看n是偶数的

那么就是不需要满足对面这个性质的

这样就可以dp了 f[i][0/1]表示dp到第i位，当前数等于或不等于第一位的方案数

然后显然可以用矩阵优化

再考虑n为奇数

用一样的思路，把环切成两半，先确定两个对应位置的值，再进行dp

f[i][0/1/2][0/1/2]表示dp到i位，下面这个数等不等于上面第一个，等不等于下面第一个（同理上面）

发现这个可以dp，依旧用矩阵优化一波

转移方程稍微有点复杂，有个对拍就轻松多了

另外注意f不能表示成f[i][0/1][0/1]表示和不同侧的起始点

原因是这样转移的时候会出现问题，无法确定它旁边的点和同侧的起始点之间的颜色关系（非常的绕口）

注意别少取模

#include 
     
      using namespace std;#define ll long longstruct re{  ll a[10][10];}aa;ll a[9][9],n,m;#define mo 998244353re XX(re x,re y){  re tmp;  memset(tmp.a,0,sizeof(tmp.a));  for (ll i=1;i<=8;i++)    for (ll j=1;j<=8;j++)      for (ll k=1;k<=8;k++)        tmp.a[i][k]+=x.a[i][j]*y.a[j][k],        tmp.a[i][k]%=mo;  return tmp;      }re fast_pow(ll x){  if (x==1) return(aa);  re b=fast_pow(x/2);  b=XX(b,b);  if (x%2==1) b=XX(b,aa);  return (b);  }int main(){  freopen("noip.in","r",stdin);  freopen("noip.out","w",stdout);  cin>>n>>m;  if (n%2==0)  {     a[1][1]=(m-4)*(m-4)+(m-3);     a[1][2]=a[1][3]=a[1][4]=a[1][7]=(m-3)*(m-4)+(m-3);      a[1][6]=a[1][8]=(m-2)*(m-3);     a[2][1]=a[2][3]=m-3;     a[2][4]=a[2][6]=a[2][7]=m-2;     a[3][2]=a[3][1]=m-3;     a[3][4]=a[3][7]=a[3][8]=m-2;     a[4][1]=a[4][7]=m-3;     a[4][2]=a[4][3]=a[4][8]=m-2;     a[7][1]=a[7][4]=m-3;     a[7][2]=a[7][3]=a[7][6]=m-2;     a[6][1]=a[6][2]=a[6][7]=a[6][8]=1;     a[8][1]=a[8][3]=a[8][4]=a[8][6]=1;          for (ll i=1;i<=8;i++)     for (ll i=1;i<=8;i++)       for (ll j=1;j<=8;j++)         aa.a[i][j]=max(0*1ll,a[i][j]%mo);      /*    for (ll i=1;i<=8;i++)     {       for (ll j=1;j<=8;j++)         cout<
      
       <<" ";       cout<