P5339 「TJOI2019」唱、跳、rap和篮球

01 / 22 / 2021 | 最后修改于 01 / 22 / 2021

OI Solution

题意

大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。他的同学可以分为四类：aa 人最喜欢唱，bb 人最喜欢跳，aa 人最喜欢rap，dd 人最喜欢篮球。如果队列中 kk，k+1k + 1，k+2k + 2，k+3k + 3 位置上的同学依次为，最喜欢唱，最喜欢跳，最喜欢rap，最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。由于合法的队伍可能会有很多种，种类数对 998244353998244353 取模。

题解

设 f(x)f(x) 为至少有 xx 组

设 g(x)g(x) 为恰好有 xx 组，答案即为 g(0)g(0)

则 f(x)=∑i=xn(ix)g(i)f(x) = \sum_{i=x}^n \binom{i}{x} g(i)

由二项式反演得 g(x)=∑i=x(−1)x−i(ix)f(x)g(x) = \sum_{i=x} (-1)^{x-i} \binom i x f(x)

f(i)=(n−3ii)⋅S(a−i,b−i,c−i,d−i)f(i) = \binom {n-3i} i \cdot S(a-i,b-i,c-i,d-i)

其中 S(a−i,b−i,c−i,d−i)S(a-i,b-i,c-i,d-i) 为 a−i,b−i,c−i,d−ia-i, b-i, c-i, d-i 自由排列的方案数

如果不考虑数量和限制，这就是多重集排列问题

先枚举每个变量取什么

∑A≤a−i,B≤b−i,C≤c−i,D≤d−i(n−4i)!A!B!C!D![A+B+C+D=n−4i]\sum_{A \le a-i, B \le b-i, C \le c-i, D \le d-i}\frac{(n-4i)!}{A!B!C!D!}[A+B+C+D=n-4i]

发现这就是4个多项式卷积，用NTT加速就好了

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
/// @tags: EGF Binom
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long ll;

int const N = 1 << 16, P = 998244353, g = 3, ig = 332748118;

int n, m, a, b, c, d, cvt[N];
int A[N], B[N], C[N], D[N], fac[N], inv[N];

inline ll qpow(ll base, int exp) {
  ll res = 1;
  while (exp) {
    if (exp & 1) res = res * base % P;
    exp >>= 1;
    base = base * base % P;
  }
  return res;
}

inline void NTT(int *const f, bool const typ, int const n) {
  for (int i = 1; i < n; ++i)
    if (i < cvt[i]) swap(f[i], f[cvt[i]]);
  for (int i = 2; i <= n; i <<= 1) {
    int mid = i >> 1, wn = qpow(typ ? g : ig, (P - 1) / i);
    for (int j = 0; j < n; j += i) {
      ll wk = 1;
      for (int k = 0; k < mid; ++k, (wk *= wn) %= P) {
        ll t = wk * f[j + k + mid] % P;
        if ((f[j + k + mid] = f[j + k] - t) < 0) f[j + k + mid] += P;
        if ((f[j + k] += t) >= P) f[j + k] -= P;
      }
    }
  }
  if (!typ) {
    ll inv = qpow(n, P - 2);
    for (int i = 0; i < n; ++i) f[i] = inv * f[i] % P;
  }
}

inline ll calc(int n, int a, int b, int c, int d) {
  if (n > a + b + c + d) return 0;
  if (n < 0) return 0;
  int maxl = 1;
  while (maxl < ((a + b + c + d) << 1)) maxl <<= 1;
  for (int i = 1; i < maxl; ++i) cvt[i] = cvt[i >> 1] >> 1 | (i & 1) * (maxl >> 1);
  for (int i = 0; i < maxl; ++i) A[i] = (i <= a) ? inv[i] : 0;
  for (int i = 0; i < maxl; ++i) B[i] = (i <= b) ? inv[i] : 0;
  for (int i = 0; i < maxl; ++i) C[i] = (i <= c) ? inv[i] : 0;
  for (int i = 0; i < maxl; ++i) D[i] = (i <= d) ? inv[i] : 0;
  NTT(A, true, maxl), NTT(B, true, maxl), NTT(C, true, maxl), NTT(D, true, maxl);
  for (int i = 0; i < maxl; ++i) A[i] = 1ll * A[i] * B[i] % P * C[i] % P * D[i] % P;
  NTT(A, false, maxl);
  return 1ll * fac[n] * A[n] % P;
}

inline ll binom(ll m, ll n) {
  if (m < n) return 0;
  return 1ll * fac[m] * inv[n] % P * inv[m - n] % P;
}

inline void init(int n) {
  n *= 2;
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % P;
  inv[n] = qpow(fac[n], P - 2);
  for (int i = n - 1; i >= 0; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % P;
}

int main() {
  cin >> n >> a >> b >> c >> d;
  int mn = min(a, min(b, min(c, d)));
  init(n);
  ll ans = 0;
  bool one = true;
  for (int i = 0; i <= min(mn, n / 4); ++i, one ^= 1) {
    ll tmp = binom(n - 3 * i, i) * calc(n - 4 * i, a - i, b - i, c - i, d - i) % P;
    ans = one ? (ans + tmp) % P : (ans + P - tmp) % P;
  }
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P5339 [TJOI2019] 唱、跳、rap和篮球.in", "cvt", stdin);
  freopen("P5339 [TJOI2019] 唱、跳、rap和篮球.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}