思路

数位DP的模板套上(其实就是dfs)
考虑如何写状态，dp[pos][status]表示现在计算到第pos位，
status是已经包含的数字，状态压缩(二进制)表示
二进制的第0位为1，表示包含数字0
第1位为1，表示包含数字1
依此类推。
好处是写起来比较方便，加入新数字可以直接用 或运算+左移运算 搞定
比如现在枚举数字2，状态是status
那么直接 ( status | (1<<2) ) ，计算结束(看上去很帅)

然后试考虑状态如何合并(剪枝)
注意到如果0123四个数字都已经出现过，那么接下来的数字只能是1和3，否则会出现0和2在1或3之后的状态，
不符合题目要求。即接下来的n-pos位没写的位置，只能是1和3的任意交错。
那么加入特判:如果四个数字都出现过，直接返回2的n-pos次方

第二个部分是核心，注意到：之后未搜索的位置填写的数字只和pos和status有关，
举个栗子，n位数字，在第四位，2003与2330与2300与2203等，只要是都只出现了023三个数字，
即pos和status相同，那么剩下的n-4位，填法都是一模一样的
so，再加入一个特判: 如果当前pos下，当前status出现过，那就可以直接返回dp值，
不必再次计算

简单的证明的话，我的想法是
题目的要求只是0和2，分别在1和3的前面，
那么，序列是否合法与前pos个数字中已经出现的数字的个数无关;
与前pos个数字中，数字出现的顺序也无关。

毕竟前pos个数字已经确定了，而且就在自己前面，前pos个数字和后面的数字，先后关系已经确定，
且这个先后关系，只和status(已经出现的数字)有关
所以可以直接把pos和status相同的合并

//最后跑了17ms ···· 真跑的飞快···  
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
LL dp[1005][20],base[1005];
int n;
LL dfs(LL pos,LL status, bool first){
    if(dp[pos][status]!=-1) return dp[pos][status];//这个值被搜索过了 返回
    if(status==(1<<4)-1) return base[n-pos];//四个数字都出现过 后面就是1 3的任意排列
    if(pos==n) return 0;//必然不满足四个数字都同时出现 否则上一行就return了

    LL res=0;
    if(first) return dfs(pos+1,(1<<2),0);//特判首位 注意到首位只能是2
    else{
        int limit=3;
        for(int i=0;i<=limit;i++){
            if(i==2 && (status&(1<<3)) ) continue;//出现3之后 不能再放2
            if(i==0 && (status&(1<<1)) ) continue;//出现1之后 不能再放0
            res=(res+dfs(pos+1,status|(1<<i),0))%mod;
        }
    }
    return dp[pos][status]=res;//赋值 + return 
}

int main(){
    memset(dp,-1,sizeof(dp));//初始化dp数组
    base[0]=1;
    for(int i=1;i<=1000;i++)//初始化2的幂次
        base[i]=base[i-1]*2%mod;
    cin>>n;
    cout<<dfs(0,0,1);
    return 0;
}

吐槽

好家伙 题解都不写数位DP 我数位DP什么时候才能站起来