P5339 【[TJOI2019]唱、跳、rap和篮球】

发表于 | 阅读数

如果队列中$k$,$k + 1$,$k + 2$,$k + 3$位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢rap、最喜欢篮球，

！同学不一样没事，类型不一样有事

假设$g(x)$为至少有$x$个蔡了，把一堆人当作总体那么放置的位置就是，那么则$C(n-3i,i)$，$\times$剩余人乱放

$\sum[a+b+c+d=n]\frac{n!}{a!b!c!d!}$

$FFT$即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 8e3 + 10;
const int mod = 998244353;

int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
int qpow(int a, int x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        x >>= 1;
        a = 1ll * a * a % mo;
    }
    return res;
}
const int P = 998244353, gi = 3;
int rev[N];
void NTT(int *A, int n, int inv)
{
    for (int i = 0; i < n; i++)
        if (i < rev[i])
            swap(A[i], A[rev[i]]);
    for (int l = 1; l < n; l <<= 1)
    {
        int tt = qpow(gi, (P - 1) / (l << 1), P);
        int temp = (inv == 1 ? tt : qpow(tt, P - 2, P));
        for (int i = 0; i < n; i += (l << 1))
        {
            int omega = 1;
            for (int j = 0; j < l; j++, omega = 1ll * omega * temp % P)
            {
                int x = A[i + j], y = 1ll * omega * A[i + j + l] % P;
                A[i + j] = inc(x, y);
                A[i + j + l] = del(x, y);
            }
        }
    }
    int invv = qpow(n, P - 2, P);
    if (inv == -1)
        for (int i = 0; i < n; i++)
            A[i] = 1ll * A[i] * invv % P;
}

int NTTinit(int n)
{
    int ML = 1, bit = 0;
    while (ML < n)
        ML <<= 1, bit++;
    for (int i = 0; i < ML; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    return ML;
}
int fac[N], facinv[N];
void prepare()
{
    fac[0] = 1;
    facinv[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    facinv[N - 1] = qpow(fac[N - 1], mod - 2, mod);
    for (int i = N - 2; i >= 1; i--)
        facinv[i] = 1ll * facinv[i + 1] * (i + 1) % mod;
}
int Calc(int x, int i)
{
    if (i == 0)
        return 1;
    if (x <= 0)
        return 0;
    if (i > x)
        return 0;

    return 1ll * fac[x] * facinv[i] % mod * facinv[x - i] % mod;
}
int A[N], B[N], C[N], D[N];
int work(int a, int b, int c, int d, int n)
{
    int ML = NTTinit(a + b + c + d + 4);
    for (int i = 0; i < ML; i++)
        A[i] = (i <= a ? facinv[i] : 0);
    for (int i = 0; i < ML; i++)
        B[i] = (i <= b ? facinv[i] : 0);
    for (int i = 0; i < ML; i++)
        C[i] = (i <= c ? facinv[i] : 0);
    for (int i = 0; i < ML; i++)
        D[i] = (i <= d ? facinv[i] : 0);
    NTT(A, ML, 1);
    NTT(B, ML, 1);
    NTT(C, ML, 1);
    NTT(D, ML, 1);
    for (int i = 0; i < ML; i++)
        A[i] = 1ll * A[i] * B[i] % mod * C[i] % mod * D[i] % mod;
    NTT(A, ML, -1);
    return 1ll * A[n] * fac[n] % mod;
}

int main()
{
    int a, b, c, d, n;
    prepare();
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    int p = min(a, min(b, min(d, c)));
    int res = 0;

    for (int i = 0; i <= p; i++)
    {
        res = inc(res, 1ll * (i & 1 ? mod - 1 : 1) * Calc(n - 3 * i, i) % mod * work(a - i, b - i, c - i, d - i, n - 4 * i) % mod);
    }
    printf("%d", res);
}