3195 有趣的数

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

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

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

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

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

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

输入格式

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

输出格式

输出只有一行，包括恰好 $n$ 位的整数中有趣的数的个数除以 $10^9+7$ 的余数。

数据范围

$4≤n≤1000$

输入样例：

4

输出样例：

3

解题思路

根据题目关系，可以将数分为两组，$(0,1)$ 和 $(2,3)$，两组之间互不影响；

我们设 $(0,1)$ 组有 $k$ 位数，则 $(2,3)$ 组有 $n-k$ 位数，首先由于每个数字都要出现至少一次，所以 $k$ 的取值范围为 $2≤k≤n-2$。

对于 $(0,1)$ 组的 $k$ 个数，由于 $0$ 必须在 $1$ 前且最高位不能为 $0$，所以这 $k$ 个数只能在后 $n-1$ 位中选，故有 $C_{n-1}^k$。

对于 $(0,1)$ 组中的 $k$ 个数，$0$ 至少有一个，且 $0$ 必须在 $1$ 前，所以排列可以为 $011\dots11,0011\dots11,\dots,00\dots001$ 共 $k-1$ 种。同理 $(2,3)$ 组有 $n-k-1$ 种可能。

故计算公式为 $\displaystyle\sum_2^{n-2}C_{n-1}^k(k-1)(n-k-1)$。

计算组合数参考代码

$C_n^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]);
  }
}
C[n][m];

参考代码

#include <iostream>
using namespace std;

const int N = 1e3 + 7;
const int 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 ans = 0;
    for (int k = 2; k <= n - 2; ++k) {
        ans = (ans + 1LL * C[n-1][k] * (k-1) % MOD * (n-k-1)) % MOD;
    }
    cout << ans;
    return 0;
}