思路
考虑有趣数的最高位的数字，0不能在首位，1不能出现在0前，3不能出现在2前，则最高位数字一定为2。
考虑在低位增加数字构造N位有趣数：
- 若数字前缀只包含2
- 向后附加0，前缀包含0，2
- 向后无法附加1，因0要在1前
- 向后附加2，前缀包含2
- 向后附加3，前缀包含2，3 - 若数字前缀包含0，2
- 向后附加0，前缀包含0，2
- 向后附加1，前缀包含0，1，2
- 向后附加2，前缀包含0，2
- 向后附加3，前缀包含0，2，3 - 若数字前缀包含2，3
- 向后附加0，前缀包含0，2，3
- 向后无法附加1，因0要在1前
- 向后无法附加2，因前缀已包含3
- 向后附加3，前缀包含2，3 - 若数字前缀包含0，1，2
- 向后无法附加0，因前缀已包含1
- 向后附加1，前缀包含0，1，2
- 向后附加2，前缀包含0，2
- 向后附加3，前缀包含0，1，2，3 - 若数字前缀包含0，2，3
- 向后附加0，前缀包含0，2，3
- 向后附加1，前缀包含0，1，2，3
- 向后无法附加2，因前缀已包含3
- 向后附加3，前缀包含0，2，3 - 若数字前缀包含0，1，2，3
- 向后无法附加0，因前缀已包含1
- 向后附加1，前缀包含0，1，2，3
- 向后无法附加2，因前缀已包含3
- 向后附加3，前缀包含0，1，2，3
问题需要求解N位数中有趣数的个数，则由上述的状态转移关系可以计算N位有趣数的个数。
例如：
- 包含012的N-1位数字，可以附加3构成N位有趣数
- 包含023的N-1位数字，可以附加1成N位有趣数
- 包含0123的N-1位数字，可以附加1，3构成N位有趣数
则状态转移过程中K位数的数量计算式为：
K位数的数量 = (sum) 可以附加1位数变为符合要求的K-1位数 * 附加数字情况的数量
实现
#include <iostream>
#define MAXN 1000000007
using namespace std;
int main() {
int N;
cin >> N;
long long s2 = 1, s02 = 0, s23 = 0,
s023 = 0, s012 = 0, s0123 = 0;
int i;
for (i = 1;i < N;++i) {
s0123 = (s0123 * 2 + s023 + s012) % MAXN;
s012 = (s012 * 2 + s02) % MAXN;
s023 = (s023 * 2 + s23 + s02) % MAXN;
s23 = (s23 + s2) % MAXN;
s02 = (s02 * 2 + s2) % MAXN;
}
cout << s0123;
}