CCF计算机职业资格认证考试题解系列文章为meelo原创，请务必以链接形式注明本文地址
CCF CSP 201312-4 有趣的数
问题描述
我们把一个数称为有趣的，当且仅当：
1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
3. 最高位数字不为0。
因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。
1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
3. 最高位数字不为0。
因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。
输入格式
输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出格式
输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3
解析
问题可以通过动态规划求解，把N位数的问题化解成为N-1位数的问题。
题目的核心是如何表示约束条件。如果N-1位数只包含0或者2，增加一位可以是0123；如果N-1位数只包含2或者3，增加一位只可能是0或者3。
根据上面的特征，动态规划的状态可以是前N-1位数只包含2、23、02、023、012、0123的个数。
题目所需求解的是包含0123数的个数。
根据题意可以推出第一个数必须为2，首先不可能是1或3，因为0需在1之前、2需在3之前，然后第一位数不能为0。
下图展示了状态的转移关系。
用矩阵可以表示为
代码
C++
#include <iostream>
#define MAXN 1000000007
using namespace std; int main() {
long long s2=, s23=, s02=, s023=, s012=, s0123=;
int N;
cin >> N;
for(int n=; n<N; n++) {
s0123 = s023 + s012 + *s0123;
s0123 %= MAXN;
s012 = s02 + *s012;
s012 %= MAXN;
s023 = s23 + s02 + *s023;
s023 %= MAXN;
s02 = s2 + *s02;
s02 %= MAXN;
s23 = s2 + s23;
s23 %= MAXN;
}
cout << s0123;
}