CCF201312-4有趣的数

题目链接：有趣的数

我们把一个数称为有趣的，当且仅当：

1. 它的数字只包含 0,1,2,3，且这四个数字都出现过至少一次。
2. 所有的 0 都出现在所有的 1 之前，而所有的 2 都出现在所有的 3 之前。
3. 最高位数字不为 0。

因此，符合我们定义的最小的有趣的数是 2013。

除此以外，4 位的有趣的数还有两个：2031 和 2301。

请计算恰好有 n 位的有趣的数的个数。

由于答案可能非常大，只需要输出答案除以 10^9^ + 7 的余数。

浅析

由题意可得，有趣的数的首位只能是2。在拼凑到n位时其中的数字有以下几种状态：

1. 只有2 ==> 后面只能放2，0，3
2. 已经有2，3 ==> 后面只能放3，0
3. 已经有2，0 ==> 后面只能放2，0，3，1
4. 已经有2，0，3 ==> 后面只能放0，1，3
5. 已经有2，0，1 ==> 后面只能放2，3，1
6. 已经有2，0，1，3 ==> 后面只能放1，3

定义一个dp数组dp[n][2][2][2]，表示在拼凑到n位时，0、1、3这3个数字分别是否已经存在（0表示不存在1表示已存在）。由上面6中状态可得出递推公式如下：

1. dp[n][0][0][0] = dp[n-1][0][0][0];
2. dp[n][0][0][1] = dp[n-1][0][0][1] + dp[n-1][0][0][0];
3. dp[n][1][0][0] = 2 * dp[n-1][1][0][0] + dp[n-1][0][0][0]; // 乘2是因为可以放0也可以放2
4. dp[n][1][0][1] = 2 * dp[n-1][1][0][1] + dp[n-1][1][0][0] + dp[n-1][0][0][1]; // 乘2是因为可以放0也可以放3
5. dp[n][1][1][0] = 2 * dp[n-1][1][1][0] + dp[n-1][1][0][0]; // 乘2是因为可以放1也可以放2
6. dp[n][1][1][1] = 2 * dp[n-1][1][1][1] + dp[n-1][1][0][1] + dp[n-1][1][1][0]; // 乘2是因为可以放1也可以放3

AC代码：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //0 1 3
        long[][][][] dp = new long[n + 1][2][2][2];
        /*
        000
        001
        100
        101
        110
        111
         */
        // 初始条件下只有2（且首位数字只能是2）
        dp[1][0][0][0] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i][0][0][0] = dp[i - 1][0][0][0];
            dp[i][0][0][1] = (dp[i - 1][0][0][1] + dp[i - 1][0][0][0]) % 1000000007;
            dp[i][1][0][0] = (2 * dp[i - 1][1][0][0] + dp[i - 1][0][0][0]) % 1000000007;
            dp[i][1][0][1] = (2 * dp[i - 1][1][0][1] + dp[i - 1][1][0][0] + dp[i - 1][0][0][1]) % 1000000007;
            dp[i][1][1][0] = (2 * dp[i - 1][1][1][0] + dp[i - 1][1][0][0]) % 1000000007;
            dp[i][1][1][1] = (2 * dp[i - 1][1][1][1] + dp[i - 1][1][0][1] + dp[i - 1][1][1][0]) % 1000000007;
        }
        long res = dp[n][1][1][1];
        System.out.println(res);
    }
}