P6561 [SBCOI2020] 人

· · 题解

一道感觉能被 cjZYZtcl 一眼秒掉的简单数数题。

题目链接

P6561 [SBCOI2020] 人

题解

我们考虑先选奇数，然后再选偶数。

那么我们需要考虑的是选出 a 个奇数后，偶数有几个位置不能选了。

普遍情况下是有 2a 个位置不能选了，但是如果你选了相邻两个奇数，比如 2x - 1 和 2x + 1，那么 2x 这个位置会被算两遍，实际情况就是只有 < 2a 个位置的偶数不能选；或者你选了 1，因为 1 的左边没有偶数了，也会导致只有 < 2a 个位置的偶数不能选。

稍加观察可以发现，我们枚举是否选奇数 1，然后可以选择的偶数位置个数只和你选择的奇数的连续段数有关。

注：这里奇数的连续段数，是指你将选出的奇数序列分成若干极长的段，使得每一段中奇数都是类似 2x + 1, 2x + 3, \cdots 这样连续的，分出来的段数即是选择的奇数的连续段数。

接下我们需要考虑如何求出奇数的连续段数为 i 时的方案数。

首先考虑不选择奇数 1 的方案数，选择奇数 1 的方案数同理可得。

我们考虑将整个序列分成 2i + 1 段，长度分别为 x_1, x_2, \cdots, x_{2i + 1}。

其实际意义就是考虑将原来的长度为 m 的奇数序列按照这个长度分成 2i + 1 段，其中 x_2, x_4, \cdots, x_{2i} 都是你选择的奇数，其余都是你没有选择的奇数。

那么按照定义，可得：

\begin{cases} x_1 + x_2 + \cdots + x_{2i + 1} = m \\ x_2 + x_4 + \cdots + x_{2i} = a \\ x_1, x_2, \cdots, x_{2i} \ge 1, x_{2i + 1} \ge 0 \end{cases}

这个方案数的计算明显可以用隔板法来解决。

组合意义可以考虑我们先将 a 个球装到对应的 i 个盒子里，然后将剩下的 m - a 个球装到剩下的 i + 1 个盒子里，每个盒子对应的限制如上所示。

那么奇数的连续段数为 i 时的方案数就是：

{a - 1 \choose i - 1} \times {m - a \choose i}

同理可得奇数的连续段数为 i，选择奇数 1 时的方案数为：

{a - 1 \choose i - 1} \times {m - a \choose i - 1}

接下来就是解决当连续段个数为 i 时，偶数能选的位置个数为多少，这个是简单的：

当不选择奇数 1 时，个数为： m - a - i。

当选择奇数 1 时，个数为：m - a - i + 1。

然后答案即为：

\sum_{i = 1} ^ a {m - a \choose i} \times {a - 1 \choose i - 1} \times {m - a - i \choose b} + \sum_{i = 1} ^ n {m - a \choose i - 1} \times {a - 1 \choose i - 1} \times {m - a - i + 1 \choose b}

直接计算的复杂度是 \Theta(Ta) 的，期望得分 50\ \text{pts}。

我们考虑推式子来优化，这里以前半部分为例，后半部分同理：

\sum_{i = 1} ^ a {m - a \choose i} \times {a - 1 \choose i - 1} \times {m - a - i \choose b}

相信在座的各位 ikun 肯定做过 P2791 幼儿园篮球题，这道题和那道题的套路很像。

发现什么都看不出来，于是把组合数拆成阶乘的形式：

\sum_{i = 1} ^ a {a - 1 \choose i - 1} \times \dfrac{(m - a)! \times (m - a - i)!}{i! \times (m - a - i)! \times b! \times (m - a - i - b)!}

然后发现 (m - a - i)! 可以约掉：

\sum_{i = 1} ^ a {a - 1 \choose i - 1} \times \dfrac{(m - a)!}{i! \times b! \times (m - a - i - b)!}

发现分母中有 i! 和 (m - a - i - b)!，要是分子中有 (m - a - b)! 就能凑成组合数了，于是分式上下同乘 (m - a - b)!。

\sum_{i = 1} ^ a {a - 1 \choose i - 1} \times \dfrac{(m - a)! \times (m - a - b)!}{i! \times b! \times (m - a - i - b)! \times (m - a - b)!}

然后把组合数再提出来：

\sum_{i = 1} ^ a {a - 1 \choose i - 1} \times {m - a - b \choose i} \times {m - a \choose b}

我们惊喜地发现最后一项是和 i 无关的，于是把它提到前面：

{m - a \choose b} \times \sum_{i = 1} ^ a {a - 1 \choose i - 1} \times {m - a - b \choose i}

由于：

{a - 1 \choose i - 1} = {a - 1 \choose a - i}

所以可得原式等于：

{m - a \choose b} \times \sum_{i = 1} ^ a {a - 1 \choose a - i} \times {m - a - b \choose i}

然后就发现后面的式子可以范德蒙德卷积了：

{m - a \choose b} \times {m - b - 1 \choose a}

选择奇数 1 的情况同理，最终推出式子为：

{m - a \choose b} \times {m - b - 1 \choose a} + {m - a \choose b} \times {m - b - 1 \choose a - 1}

至此，时间复杂度优化为 \Theta(T + m)，期望得分 100\ \text{pts}。

代码实现

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 998244353;
int fac[5000005], ifac[5000005];
int qpow(int x, int p) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = 1ll * ans * x % mod;
        p >>= 1, x = 1ll * x * x % mod;
    }
    return ans;
}
int C(int m, int n) {
    if (n > m or n < 0 or m < 0) return 0;
    return 1ll * fac[m] * ifac[n] % mod * ifac[ m - n ] % mod;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
    fac[0] = 1;
    for (int i = 1; i <= 5e6; ++i) fac[i] = 1ll * fac[ i - 1 ] * i % mod;
    ifac[5000000] = qpow(fac[5000000], mod - 2);
    for (int i = 5e6; i; --i) ifac[ i - 1 ] = 1ll * ifac[i] * i % mod;
    int t; cin >> t;
    while (t--) {
        int a, b, m; cin >> m >> a >> b;
        cout << 1ll * C(m - a, b) * (C(m - b - 1, a) + C(m - b - 1, a - 1)) % mod << '\n';
    }
    return 0;
}