Acw1359 有趣的数

Acw1359 有趣的数

条件

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

题解

• 对于条件 $2$

• 把条件 2 划分为两类

• 0.1 设有 $k$ 位

• 2.3 设有 $n-k$ 位

• 由于最高位不是 0 ，所以0在1之前不可以在第一位

• 因为四个数字至少出现一次，所以 $k$ 最多只能有 $n-2$ 位

于是我们得到了 $k$ 的范围
$$ k\ge 2 \ and \ k\le n-2 ，所以 2\le k \le n-2 $$

• 对于条件 $2$ 的每一类

我们再对 $k$ 位的 0 1 数进行分类

1. 设 0 的个数为 $a$ 个，那么，1 的个数就是 $k-a$ 个
2. 由于每个数至少出现一次，所以 $a$ 的范围是 $1\le a\le k-1$
3. 所以，$k$ 位的 0 1 数总共有 $k-1$ 种选法

$n-k$ 的 2 3 数同理，总共有 $n-k-1$ 种选法 $\to$ 可以根据 0 1 数的选法获得

• 计算答案

对于每一个 $k(2\le k \le n-2)$ 分别计算答案

$$ ans=\sum^{n-2}_{k=2} C_{n-1}^k(k-1)(n-k-1) $$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define debug(a) cout << #a << " " << a << endl
const int maxn = 1e5 + 7;
const int N = 1010, M = N * 2;
const int inf = 0x3f3f3f3f;
const long long 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 == 0) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }

    ll res = 0;
    for(int k = 2; k <= n - 2; k++) {
        res = res + (C[n - 1][k] * (k - 1) % mod * (n - k - 1)) % mod;
        res %= mod;
    }

    cout << res << '\n';

    return 0;
}