题目链接：LOJ 3106

大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。

他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢 rap，还有一部分最喜欢篮球。如果队列中 $k, k + 1, k + 2, k + 3$ 位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢 rap、最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。

大中锋不希望这种事情发生，因为这会使得队伍显得很乱。

大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。

由于合法的队伍可能会有很多种，种类数对 $998244353$ 取模。

数据范围：$1 \le n \le 1000$，$0 \le a, b, c, d \le 500$，$a + b + c + d \ge n$。

Solution

考虑容斥。我们设 $f(i)$ 表示至少有 $i$ 组人在讨论蔡徐坤的方案数，很显然至多有 $m = \min\{\left\lfloor\frac{n}{4}\right\rfloor, a, b, c, d\}$ 组人。

那么答案为：

$$ \sum_{i = 0} ^ {m} (-1) ^ {i} f(i) $$

接下来考虑如求 $f(i)$ 的值。首先我们从 $n$ 个人中强制选出 $i$ 组人讨论蔡徐坤，考虑把一组人缩成一个人，那么一共有 $n - 3i$ 个人，要在其中选择 $i$ 个人，则方案数为 $\binom{n - 3i}{i}$，而剩下的 $n - 4i$ 个人是随意排列的，相当于一个可重集排列方案数。我们枚举每种人分别有多少个，方案数可以表示为如下式子：

$$ \sum_{i_{1} = 0} ^ {a - i} \sum_{i_{2} = 0} ^ {b - i} \sum_{i_{3} = 0} ^ {c - i} \sum_{i_{4} = 0} ^ {d - i} [i_{1} + i_{2} + i_{3} + i_{4} = n - 4i] \frac{(n - 4i)!}{i_{1}! \cdot i_{2}! \cdot i_{3}! \cdot i_{4}!} $$

发现这是一个四元卷积的形式，可以直接 $\mathcal O(n \log n)$ 求出。

时间复杂度：$\mathcal O(n ^ {2} \log n)$。

Code

/* 此处省略多项式模板 */

const int N = 1e3 + 5;

int n, a, b, c, d, fac[N], ifac[N];

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
}
int C(int n, int m) {
    return 1LL * fac[n] * ifac[n - m] % MOD * ifac[m] % MOD;
}
int calc(int tot, int a, int b, int c, int d) {
    if (a + b + c + d < tot) return 0;
    int n = (a++) + (b++) + (c++) + (d++) + 1, N = extend(n);
    Vec A(a, 0), B(b, 0), C(c, 0), D(d, 0);
    for (int i = 0; i < a; i++) A[i] = ifac[i];
    for (int i = 0; i < b; i++) B[i] = ifac[i];
    for (int i = 0; i < c; i++) C[i] = ifac[i];
    for (int i = 0; i < d; i++) D[i] = ifac[i];
    A.resize(N), DFT(A);
    B.resize(N), DFT(B);
    C.resize(N), DFT(C);
    D.resize(N), DFT(D);
    for (int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % MOD * C[i] % MOD * D[i] % MOD;
    IDFT(A), A.resize(n);
    return A[tot];
}
int main() {
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    init(n);
    int m = std::min(n / 4, std::min(std::min(a, b), std::min(c, d)));
    int ans = 0;
    for (int i = 0, sgn = 1; i <= m; i++, sgn = MOD - sgn) {
        int s = calc(n - 4 * i, a - i, b - i, c - i, d - i);
        add(ans, 1LL * sgn * C(n - 3 * i, i) % MOD * fac[n - 4 * i] % MOD * s % MOD);
    }
    printf("%d\n", ans);
    return 0;
}