icpc 2018 焦作L-Poor God Water

• 题意：

• 有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;
  }
  

```