• 思路：此题有三种做法，分别可以用数位dp，有限状态机dp，组合数学。

• 解析：

• 数位dp做法：

  • 因为可能出现的数字只有$4$种，所以可以用二进制表示出现数字的状态，例如$0001$表示$0$已经出现，$0010$表示$1$已经出现,$0100$表示$2$已经出现，$1000$表示$3$已经出现。举个例子，要想表示$3$在这一位出现，状态变化可以是$preState | (1 << 3)$，当然也可以是$preState | 8$。然后保证出现1后不能再出现0，出现3后不能再出现2并且第一位只能是$2$。最后还有一种情况就是当所有数字均出现过后，剩下的位置可以放$1, 3$任意组合。

  • 毕竟是数位dp，所以用dfs的做法必然是要记忆化搜索的，这样可以降低时间复杂度，这里用$dp_{pos, st}$表示在第$pos$位时状态为$st$的方案数，比如说当前位已经出现了$2, 0, 1$，那么在这位之后所能放的方案肯定一样的，举个例子，比如当前的数为$2201, 2012, 2001$那么他们之后的方案数必然一样，这时候只用算一个即可，其他的就可以被剪枝。

  • 代码：

      #include<iostream>
      #include<cstdio>
      #include<cstring>
      using namespace std;
      typedef long long ll;
      const int N = 1005;
      const ll mod = 1e9 + 7;
      int n;
      ll dp[N][50];

      ll qpow(ll a, ll x)
      {
          ll ans = 1;
          while(x)
          {
              if(x & 1) ans = ans * a % mod;
              a = a * a % mod;
              x >>= 1;
          }
          return ans;
      }

      ll dfs(int pos, int st) //pos：第几位, st:0001表示0已经出现，0010表示1已经出现,0100表示2已经出现，1000表示3已经出现
      {
          ll res = 0;
          if(pos == n + 1) return 0; //仍然不满足条件
          if(dp[pos][st] != -1) return dp[pos][st]; //剪枝
          if(st == 15) return dp[pos][st] = qpow(2, n - pos); //0，1，2，3全出现过了，那么剩下随便放1，3(2^x种方案)
          for(int i = 0; i <= 3; i++)
          {
              if(i == 0 && (st & 2)) continue; //此位填0，则之前不能出现1
              if(i == 2 && (st & 8)) continue; //此位填2，之前不能出现3
              res = (res % mod + dfs(pos + 1, (1 << i) | st) % mod) % mod;
          }
          return dp[pos][st] = res;
      }

      int main()
      {
          memset(dp, -1, sizeof dp);
          cin >> n;
          ll res = dfs(1, 4);
          cout << res << endl;
          return 0;
      }

• 有限状态机做法：

  • 用$st_{i, j}$表示前$i$个数在状态$j$下的方案数。可以一共分为6种状态：
  • $j = 0$：2已用，0, 1, 3未用；
  • $j = 1$：2,0已用，1, 3未用；
  • $j = 2$：2,3已用，0, 1未用；
  • $j = 3$：2,1,0已用，3未用；
  • $j = 4$：2,3,0已用，1未用；
  • $j = 5$：全部数字均被使用。

  那么转移方程见代码，这里举个例子：当$j = 4$时，$st_{i, j} = st_{i - 1, 1} + st_{i - 1, 2} + st_{i - 1, 4} * 2$。因为此时$2、3、0$均使用，那么可以由$i = i - 1, j = 1$时的情况，并且在这位放$3$或者由$i = i - 1, j = 2$时的情况，并且在这位放$0$，还可以是$i = i - 1, j = 4$时的情况，那么在这位可以放$0/3$。

  最后答案为$st_{n, 5}$。

  • 代码：

      #include<iostream>
      #include<cstdio>
      using namespace std;
      typedef long long ll;
      const int N = 1005;
      const ll mod = 1e9 + 7;
      int n;
      ll st[N][10];

      /*
      开头只能是2
      State:
      0: 2用, 0,1,3未用
      1: 2,0用， 1,3未用
      2: 2,3用，0,1未用
      3: 2,1,0用，3未用
      4: 2,3,0用, 1未用
      5: 全用
      */

      int main()
      {
          cin >> n;
          for(int i = 1; i <= n; i++)
          {
              st[i][0] = 1;
              st[i][1] = (st[i - 1][0] + st[i - 1][1] * 2) % mod; //第i个选0/(0, 2任意)
              st[i][2] = (st[i - 1][0] + st[i - 1][2]) % mod;
              st[i][3] = (st[i - 1][1] + st[i - 1][3] * 2) % mod;
              st[i][4] = (st[i - 1][1] + st[i - 1][2] + st[i - 1][4] * 2) % mod;
              st[i][5] = (st[i - 1][3] + st[i - 1][4] + st[i - 1][5] * 2) % mod;
          }
          cout << st[n][5] << endl;
          return 0;
      }

• 组合数做法：

  • 首先将数字分为两组，分别是$A = \{0, 1\}，B = \{2, 3\} ​$。假设属于$A​$的个数有$k(2 \le k \le n - 2)​$个，那么属于$B​$的则有$n - k​$个，因为第一个只能放$2​$，那么剩下$n - 1​$个位置不确定，又因为$0​$必须在$1​$前面（顺序已经确定），所以$A​$组的摆放方案可以是$C_{n -1}^k \times (k - 1)​$，$(k - 1)​$代表有$1个0，2个0…k - 1个0​$一共$k -1​$个方案，那么$B​$组的顺序也是确定的，$2​$必须在$3​$的前面，所以方案数为$(n - k - 1)​$，代表有$1个2，2个2…(n -k - 1)个2​$一共$n - k -1​$个方案。所以最终答案为：$\sum_{k = 2}^{n - 2}C_{n -1}^k \times (k - 1)\times (n - k -1)​$。

  • 代码：

      #include<iostream>
      #include<cstdio>
      using namespace std;
      typedef long long ll;
      const int N = 1000;
      const ll mod = 1e9 + 7;
      ll c[N + 5][N + 5];
      int n;
      ll res = 0;

      void Init()
      {
          cin >> n;
          for(int i = 0; i <= N; i++)
          {
              for(int j = 0; j <= i; j++)
              {
                  if(!j) c[i][j] = 1;
                  else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
              }
          }
      }

      int main()
      {
          Init();
          for(int i = 2; i <= n - 2; i++)
              res = (res % mod +  c[n - 1][i] * (i - 1) * (n - i - 1) % mod) % mod;
          cout << res << endl;
          return 0;
      }