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

GKxx

2019-07-30 11:36:50

Solution

老年退役选手来写题解了 ### 题意 有$a$个人喜欢唱,$b$个人喜欢跳,$c$个人喜欢rap,$d$个人喜欢篮球,现在要从中选出$n$个人排成一队,使得不存在位置$k$满足第$k$,$k+1$,$k+2$,$k+3$个人依次喜欢唱、跳、rap、篮球,求方案数。 两种方案不同,当且仅当有一个位置上的同学的喜好不同。 ### 题解 为了方便,我们将连续的唱跳rap篮球四个人称为“ikun段”。 现在要计算没有ikun段的方案数并不方便,可以考虑容斥,那么答案显然是 $$ans=\sum\limits_{i=0}^{\min\{a,b,c,d,\lfloor\frac{n}{4}\rfloor\}}(-1)^if(i)$$ 其中$f(i)$表示指定$i$处ikun段,其它地方任意排列的方案数。 要指定$i$处ikun段,注意到它们不能相交,设第$j$处ikun段的开头位置为$a_j$,显然有 $$a_j+3<a_{j+1}$$ $$1\leq a_1,a_i+3\leq n$$ 简单整理一下可以得到 $$1\leq a_1<a_2-3<a_3-6<\cdots<a_j-3(j-1)\leq n-3i$$ 因此方案数就是$C_{n-3i}^i$。 指定了$i$处出现ikun段之后,剩下$n-4i$个位置任意排列,也就是从$a-i$个唱、$b-i$个跳、$c-i$个rap、$d-i$个篮球中选出$n-4i$个来排列。这个问题是经典的指数型生成函数问题,答案就是$h(x)$的项$x^{n-4i}$的系数乘上$(n-4i)!$,其中 $$h(x)=\left(\sum\limits_{j=0}^{a-i}\frac{x^j}{j!}\right)\left(\sum\limits_{j=0}^{b-i}\frac{x^j}{j!}\right)\left(\sum\limits_{j=0}^{c-i}\frac{x^j}{j!}\right)\left(\sum\limits_{j=0}^{d-i}\frac{x^j}{j!}\right)$$ NTT求卷积即可。 总结一下,我们要求的东西就是 $$ans=\sum\limits_{i=0}^{\min\{a,b,c,d,\lfloor\frac{n}{4}\rfloor\}}(-1)^iC_{n-3i}^i(n-4i)![x^{n-4i}]h(x)$$ 组合数的分母也含有$(n-4i)!$,可以约去,但这其实无所谓。 枚举$i$,求卷积$O(n\log n)$,总复杂度$O(n^2\log n)$ ~~我怀疑这题暴力求卷积+卡常优化可以比NTT快~~ ```cpp #include <cctype> #include <cstdio> #include <climits> #include <algorithm> template <typename T> inline void read(T &x) { int f = 0, c = getchar(); x = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = x * 10 + c - 48, c = getchar(); if (f) x = -x; } template <typename T, typename... Args> inline void read(T &x, Args&... args) { read(x); read(args...); } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <typename T> inline void writeln(T x) { write(x); puts(""); } template <typename T> inline bool chkmin(T &x, const T &y) { return y < x ? x = y, 1 : 0; } template <typename T> inline bool chkmax(T &x, const T &y) { return x < y ? x = y, 1 : 0; } typedef long long LL; const int maxn = 1e3 + 7; const LL P = 998244353, G = 3, Gi = 332748118; inline LL qpow(LL x, LL k) { LL s = 1; for (; k; x = x * x % P, k >>= 1) if (k & 1) s = s * x % P; return s; } inline void ntt(LL *A, int *r, int lim, int tp) { for (int i = 0; i < lim; ++i) if (i < r[i]) std::swap(A[i], A[r[i]]); for (int mid = 1; mid < lim; mid <<= 1) { LL wn = qpow(tp == 1 ? G : Gi, (P - 1) / (mid << 1)); for (int j = 0; j < lim; j += mid << 1) { LL w = 1; for (int k = 0; k < mid; ++k, w = w * wn % P) { LL x = A[j + k], y = w * A[j + k + mid] % P; A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P; } } } if (tp == -1) { LL inv = qpow(lim, P - 2); for (int i = 0; i < lim; ++i) A[i] = A[i] * inv % P; } } int a, b, c, d, n, mn, mx; LL fac[maxn], ifac[maxn]; LL ha[maxn << 3], hb[maxn << 3], hc[maxn << 3], hd[maxn << 3]; int r[maxn << 3]; inline LL g(int i) { std::copy(ifac, ifac + a - i + 1, ha); std::copy(ifac, ifac + b - i + 1, hb); std::copy(ifac, ifac + c - i + 1, hc); std::copy(ifac, ifac + d - i + 1, hd); int lim = 1, l = 0; while (lim <= a + b + c + d - 4 * i) lim <<= 1, ++l; for (int j = 0; j < lim; ++j) r[j] = (r[j >> 1] >> 1) | ((j & 1) << (l - 1)); ntt(ha, r, lim, 1); ntt(hb, r, lim, 1); ntt(hc, r, lim, 1); ntt(hd, r, lim, 1); for (int j = 0; j < lim; ++j) ha[j] = ha[j] * hb[j] % P * hc[j] % P * hd[j] % P; ntt(ha, r, lim, -1); LL ret = ha[n - 4 * i]; std::fill(ha, ha + lim, 0); std::fill(hb, hb + lim, 0); std::fill(hc, hc + lim, 0); std::fill(hd, hd + lim, 0); return ret; } int main() { read(n, a, b, c, d); mn = std::min({a, b, c, d, n / 4}); mx = std::max({a, b, c, d, n}); fac[0] = ifac[0] = 1; for (int i = 1; i <= mx; ++i) fac[i] = fac[i - 1] * i % P; ifac[mx] = qpow(fac[mx], P - 2); for (int i = mx - 1; i; --i) ifac[i] = ifac[i + 1] * (i + 1) % P; LL ans = 0; for (int i = 0; i <= mn; ++i) { LL sgn = i & 1 ? P - 1 : 1; LL res = sgn * fac[n - 3 * i] % P * ifac[i] % P * g(i) % P; ans = (ans + res) % P; } writeln((ans % P + P) % P); return 0; } ```