有趣的数

算法 , CCF
,

参考链接：https://blog.csdn.net/readlnh/article/details/51058005

问题描述

　　我们把一个数称为有趣的，当且仅当： 　　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

这题是典型的数位dp， 将其分为6种状态如下：注意箭头右边是栗子，注意n个数是由n-1个数加一个数组成的

  1. 只含2 => 222_2
  2. 只含2、0 => 222_0、 2020_2、 2020_0
  3. 只含2、3 => 2333_3、222_3
  4. 只含2、0、1 => 2200_1、220011_2、220011_1
  5. 只含2、0、3 => 2233_0、2200_3、223300_0、223300_3
  6. 含4种数字 => 201_3、203_1、2013_3、 2013_1、2031_1、2031_3

dp[i][j]表示位数为 i，符合状态 j 的（6种）合法的数的个数。

对于状态2: dp[i][2] = dp[i-1][1] + dp[i-1][2] * 2

位数为 i 且只含 2、0 的整数可以由位数为 i-1 的只含 2 的数在末尾添加0 得到，也可以通过 位数 i-1 的只含0、2 的数在末尾添加 0、2 组成

对于转态3：dp[i][3] = dp[i-1][1] + dp[i-1][3]

位数为i 且只含2、3 的整数可以由 位数为 i-1 的只含 2 的数在末尾添加3得到，也可以通过位数为 i-1 的 (2)+(3)* 在末尾添加3得到

注：1. (2)+(3)* 是正则表达式形式； 2. 数字2必须在3之前

对于状态4: dp[i][4] = dp[i-1][2] + dp[i-1][4] * 2

对于状态5：dp[i][5] = dp[i-1][2] + dp[i-1][3] + dp[i-1][5] * 2

对于状态6：dp[i][6] = dp[i-1][4] + dp[i-1][5] + dp[i-1][6] * 2

要强调一点，2肯定是在首位的，因为2必须在3的前面，而0必须在1的前面，而且0不能在首位，那么显而易见的首位只能是2.

#include <iostream>
#include <cstring>
#define LL long long
using namespace std;    


const int MOD = 1000000007;
LL dp[1001][7];

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