图片说明
图片说明

  • 题意：

  • 有N个小时，有三种食物（用1 ，2 ，3代替好了），每个小时要吃一种食物，要求任意连续三个小时不能出现111，222，333，132，231，313，323的方案数

  • 题解：

  • 对于 n 来说，我们只关注后两位，因为 若 n - 1 的所有方案解决的话，我们在 n - 1 的方案添加0, 1,2 就行，然后根据禁忌 去除不可能的

  • 代码:

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
const int n = 9;
struct node{
  ll m[9][9];
};
node e;
node mul(node x,node y)
{
  node c;
  for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
          c.m[i][j] = 0;
  for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
          for(int k=0;k<n;k++)
              c.m[i][j] = c.m[i][j]%mod + x.m[i][k]*y.m[k][j]%mod;
  return c;
}
node pow(node x,ll y)
{
  for(int i=0;i<n;i++)
      e.m[i][i] = 1;
  node ans = e;
  while(y)
  {
      if(y&1)
          ans = mul(ans,x);
      x = mul(x,x);
      y>>=1;
  }
  return ans;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      ll z,cnt = 0,k = 0;
      scanf("%lld",&z);
      if(z == 1)
          printf("3\n");
      else if(z == 2)
          printf("9\n");
      else{
          node res,ans = {
              0,0,0, 1,0,0, 1,0,0,
              1,0,0, 0,0,0, 1,0,0,
              1,0,0, 1,0,0, 1,0,0,

              0,1,0, 0,1,0, 0,0,0,
              0,1,0, 0,0,0, 0,1,0,
              0,0,0, 0,1,0, 0,1,0,

              0,0,1, 0,0,1, 0,0,1,
              0,0,1, 0,0,0, 0,0,1,
              0,0,1, 0,0,1, 0,0,0
          };
          res = pow(ans,z-2);
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<n;j++)
              {
                  k += res.m[i][j];
                  k %= mod;
              }
          }
          cout<<k<<endl;
      }
  }
  return 0;
}

```