题目描述

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

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

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

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

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

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

输入格式
输入只有一行，包括恰好一个正整数 n。

输出格式
输出只有一行，包括恰好 n 位的整数中有趣的数的个数除以 109+7 的余数。

数据范围
$4≤n≤1000$

样例

输入样例：

4

输入样例：

4

算法1

(组合计数) $O(n^2)$

根据题意可依次分析：

• 0,1,2,3均必须出现一次或一次以上，设总数为n。
• 0,1 可看作一组， 2,3 可看作一组，则设0,1数量之和为 m，则m范围为$ 2 \le m \le n-2 $ 。
• 且0不能放在开头处，则根据组合计数可知0，1放的位置为$ C_{n - 1}^{m} $ 此时2,3的位置也相应确定。
• 且对于0,1组内部可选的组合为$m-1$种，相应2,3组可选的组合数为$ n-m-1 $种。
• 因此最后的结果为枚举m，求每个m 下 $ C_{n - 1}^{m} * (m - 1) * (n - m - 1) $ 然后求和即为答案。

注意点：

• long long 范围
• 注意取模
• 组合数的计算可采用DP方法求解 $ C(n, m) = C(n - 1, m) + C(n - 1, m - 1) $

时间复杂度

DP求组合数的时间复杂度为 $O(n^2)$

C++ 代码

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1010, MOD = 1e9 + 7;

int n;
int C[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

    int res = 0;
    for (int i = 2; i <= n - 2; i ++ )
    {
        res += (LL)C[n - 1][i] * (i - 1) % MOD * (n - i - 1) % MOD;
        res %= MOD;
    }
    cout << res << endl;
    return 0;
}