「TJOI 2019」唱、跳、rap 和篮球（容斥原理）

题目大意

「TJOI 2019」唱、跳、rap 和篮球（Luogu 5339）

共有 $a + b + c + d$ 个人，有 $a$ 个人喜欢唱，有 $b$ 个人喜欢跳，有 $c$ 个人喜欢 rap，有 $d$ 个人喜欢篮球。要求选出 $n$ 个人排队，使得不存在一个位置 $i$，满足位置 $i, i + 1, i + 2, i + 3$ 上的人同时喜欢唱、跳、rap 和篮球。我们称两种方案不同当且仅当有一个位置上的人的爱好不同，求共有多少不同的方案 $\bmod 998244353$ 的结果。

数据范围：$n \le 10^3, a, b, c, d \le 500$。

思路分析

网上好多题解都是 $O(n^2 \log n)$ 的，这里讲一个 $O(n^2)$ 的做法。

我们记唱为 C，跳为 T，rap 为 R，篮球为 L，位置 $i, i + 1, i + 2, i + 3$ 上的人同时喜欢唱、跳、rap 和篮球的组叫坤坤组。考虑枚举坤坤组的数量 $k$，然后除了 $k$ 个坤坤组的位置随便选，最后的答案就是 $\sum_{k} (-1)^k \times \sum_{\text{queue}} [\text{cnt_kun(queue)} = k]$。

对于某个 $k$，我们先要选出 $k$ 个坤坤组的位置。考虑 $k$ 个坤坤组形成的位置集合 ${ p_1, p_2, \cdots, p_k }$，我们将 $p_i \leftarrow p_i - 3(i - 1)$ 后，限制就变成了 $1 \le p_1 < p_2 < \cdots < p_k \le n - 3k$，所以方案数就是 $\binom{n - 3k}{k}$。

接下来我们考虑剩下的位置。此时，假设我们还剩 $C = a - k$ 个 C，$T = b - k$ 个 T，$R = c - k$ 个 R，$L = d - k$ 个 L，要把他们放到 $m = n - 4k$ 个位置中。我们可以将其看作是一个多项式 $A = (x + y + z + w)^m$，将计算结果中 $x$ 次数不超过 $C$，$y$ 次数不超过 $T$，$z$ 次数不超过 $R$，$w$ 次数不超过 $L$，的所有项的系数相加就可以得到答案。我们将其展开，得到答案为：

$$\sum_{i = 0}^{m} \binom{m}{i} \left( \sum_{j = 0}^{i} \binom{i}{j} \cdot [j \le C] \cdot [i - j \le T] \right) \left( \sum_{j = 0}^{m - i} \binom{m - i}{j} \cdot [j \le R] \cdot [m - i - j \le L] \right)$$

对于外层的求和可以枚举，对于内层的求和，发现一定可以写成 $\sum_{i = l}^{r} \binom{x}{i}$ 的形式。预处理组合数前缀和即可，时间复杂度 $O(n^2)$。

代码实现

一个坑点是 $k$ 必须循环到 $\min {\displaystyle \frac{n}{4}, a, b, c, d}$，如果再大会出错。

#include <bits/stdc++.h>