原题链接

ACwing

思路

一个直观的想法是，如果我们知道长度为的有趣的数的个数，是否可以知道长度为的有趣的数个数？简单思考，容易发现，如果只知道有趣的数个数，是不足以完成递推的，例如题目中给出的4位有趣的数，并不是所有5位有趣的数的前缀。然而，如果我们可以枚举所有可行前缀的个数 ，就可以完成递推，并且由于前缀是唯一的，故而递推结果不会重复。

哪些前缀是可行的？题目中的约束简单说来，就是第一个数字必须是2，0必须在1之前，2必须在3之后。故而：

  1. 对于任意前缀，2必然存在其中；
  2. 只可能缺少1/3/1,3/0,1/0,1,3这些数字组合。

故而，我们可以将前缀分为6种，除了上述的5种缺少数字的组合之外，还应该有全部数字都存在的情况。简单思考，这样的状态是合理的，满足最优子结构。为了讨论的方便起见，我们不妨将6种状态记为：

1
2
3
4
5
6
0 全有
1 缺3
2 缺1
3 缺13
4 缺01
5 缺013

接下来思考状态如何转移。

  1. 状态0可以通过自身（后缀为1,3）以及1、2两个状态转移（后缀为缺少的数字）；
  2. 状态1可以通过自身（后缀为2,1）以及状态3转移；
  3. 状态2可以通过自身（后缀为0，3）以及状态3,4转移；
  4. 状态3可以通过自身（后缀为0,2）以及状态5转移；
  5. 状态4可以通过自身（后缀为3）以及状态5转移；
  6. 状态5只可以通过自身转移。

容易发现，上述每一个状态只依赖编号大于等于它的状态，故而可以只使用一个大小为6的数组完成状态转移。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1000000000 + 7;
ll dp[6];


int main(){
    int n;
    cin>>n;
    memset(dp, 0, sizeof dp);
    
    dp[5] = 1;
    for(int i=2;i<=n;i++){
        dp[0] = (2*dp[0] + dp[1] + dp[2])%MOD;
        dp[1] = (dp[3] + 2*dp[1])%MOD;
        dp[2] = (2*dp[2] + dp[3] +dp[4])%MOD;
        dp[3] = (2*dp[3] + dp[5])%MOD;
        dp[4] = (dp[4] + dp[5])%MOD;
        dp[5] = (dp[5])%MOD;
        
    }
    
    cout<<dp[0]<<endl;
    return 0;
}