题意就不用讲了吧……
鸡你太美！！！
题意：有 \(4\) 种喜好不同的人，分别最爱唱、跳、 \(rap\)、篮球，他们个数分别为 \(A,B,C,D\) ，现从他们中挑选出 \(n\) 个人并进行排列，规定不能出现喜爱唱、跳、 rap、篮球的人在序列中依次出现，问合法方案数。
下文将喜爱唱、跳、 \(rap\)、篮球的人依次出现的区间称为聚集区间，长度为 \(4\)。
思路（容斥原理 + 生成函数 + \(\mathcal{NTT}\)）首先，我们可以发现如果顺着求方案数并不好求。秉持顺难逆易的原则，我们可以考虑容斥，令 \(f(k)\) 表示在长度为 \(n\) 的序列中出现了至少 \(k\) 个聚集区间的方案数，进而我们得出：\(Answer=\displaystyle\sum_{k}(-1)^{k}f(k)\)。
接下来，我们的目标就是求出 \(f(k)\)。我们可以设这 \(k\) 个聚集区间的起始位置 \(i\)，并把 \(i,i+1,i+2,i+3\) 缩为一个点，这样就一共剩下 \(n-3k\) 个点，接着，我们就可以从这 \(n-3k\) 个点中选取不在聚集区间内的点，这样的点一共有 \(n-4k\) 个，所以方案数为 \(\binom{n-3k}{n-4k}=\binom{n-3k}{k}\)。
我们设 \(S(a,b,c,d,n)\) 表示 \(4\) 种人的数量分别有 \(a,b,c,d\) 个，从中挑选出 \(n\) 个人并进行排列的方案数。所以，\(f(k)=\binom{n-3k}{k}S(A-k,B-k,C-k,D-k,n-4k)\)
随后，我们把注意力放在 \(S(a,b,c,d,n)\) 上，可以发现这与指数型生成函数 \(EGF\) 的应用场景非常类似。所以，我们可以写出每种人的生成函数，例如第一种人的生成函数为 \(\displaystyle\sum_{k}^{a}\dfrac{x^k}{k!}\)。接着，我们将这四种人的生成函数进行卷积，而其中的第 \(n\) 项的系数就是答案，即 \([x^{n}]\displaystyle\sum_{k}^{a}\dfrac{x^k}{k!}\displaystyle\sum_{k}^{b}\dfrac{x^k}{k!}\displaystyle\sum_{k}^{c}\dfrac{x^k}{k!}\displaystyle\sum_{k}^{d}\dfrac{x^k}{k!}\)
综上，\(Answer=\displaystyle\sum_{k}(-1)^{k}f(k)=\displaystyle\sum_{k}(-1)^{k}\binom{n-3k}{k}S(A-k,B-k,C-k,D-k,n-4k)\)
时间复杂度如果卷积时使用 \(\mathcal{NTT}\)，时间复杂度约为 \(n^2\log_2n\)。但由于数据不强，时限宽松，暴力进行卷积也可通过，时间复杂度约为 \(n^3\)。
听说还有使用其它方法 \(AC\) 的 \(n\sqrt{n}\) 的算法，蒟蒻不会太强了%%%
代码实现： #include <map> #include <cmath> #include <ctime> #include <queue> #include <cstdio> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define LL long long #define Int register int #define Lc(x) Child[x][0] #define Rc(x) Child[x][1] #define Swap(a, b) a ^= b ^= a ^= b #define Abs(x) ((x) < 0 ? -(x) : (x)) #define Max(x, y) ((x) < (y) ? (y) : (x)) #define Min(x, y) ((x) < (y) ? (x) : (y)) #define Isdigit(ch) (ch >= '0' and ch <= '9') const int MAXN = 1e3 + 10; const double Pi = acos (-1.0); const LL Mod = 998244353, G = 3, Inv2 = 499122177, INF = 1LL << 60; inline LL Read () { LL f = 0, x = 0; char ch = getchar (); while (!isdigit (ch) ) { f |= (ch == '-'), ch = getchar (); } while (isdigit (ch) ) { x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar (); } return f ? -x : x; } inline void Write (const LL &x) { if (x < 0 ) { putchar ('-'), Write (-x); return ; } if (x > 9 ) { Write (x / 10); } putchar ((x % 10) ^ 48); return ; } LL Answer; int n, a, b, c, d; LL Fact[MAXN], Inv[MAXN], Pow[MAXN], Sum1[MAXN], Sum2[MAXN]; inline LL Qkpow (LL Base, LL x) { LL Total = 1; while (x ) { if (x & 1 ) { Total = Total * Base % Mod; } Base = Base * Base % Mod, x >>= 1; } return Total; } inline LL Getinv (const LL x) { return Qkpow (x, Mod - 2); } inline LL Getbinom (const int n, const int m) { return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod; } inline LL Clac (const int a, const int b, const int c, const int d, const int n) { Int i, j; for (i = 0; i <= n; ++ i ) { Sum1[i] = Sum2[i] = 0; } Sum1[0] = 1; for (i = 0; i <= n; ++ i ) { for (j = 0; j <= a and i + j <= n; ++ j ) { Sum2[i + j] = (Sum2[i + j] + Sum1[i] * Inv[i] % Mod * Fact[i + j] % Mod * Inv[j] % Mod) % Mod; } } for (i = 0; i <= n; ++ i ) { Sum1[i] = Sum2[i], Sum2[i] = 0; // printf ("%lld ", Sum1[i]); } // putchar ('\n'); for (i = 0; i <= n; ++ i ) { for (j = 0; j <= b and i + j <= n; ++ j ) { Sum2[i + j] = (Sum2[i + j] + Sum1[i] * Inv[i] % Mod * Fact[i + j] % Mod * Inv[j] % Mod) % Mod; } } for (i = 0; i <= n; ++ i ) { Sum1[i] = Sum2[i], Sum2[i] = 0; // printf ("%lld ", Sum1[i]); } // putchar ('\n'); for (i = 0; i <= n; ++ i ) { for (j = 0; j <= c and i + j <= n; ++ j ) { Sum2[i + j] = (Sum2[i + j] + Sum1[i] * Inv[i] % Mod * Fact[i + j] % Mod * Inv[j] % Mod) % Mod; } } for (i = 0; i <= n; ++ i ) { Sum1[i] = Sum2[i], Sum2[i] = 0; // printf ("%lld ", Sum1[i]); } // putchar ('\n'); for (i = 0; i <= n; ++ i ) { for (j = 0; j <= d and i + j <= n; ++ j ) { Sum2[i + j] = (Sum2[i + j] + Sum1[i] * Inv[i] % Mod * Fact[i + j] % Mod * Inv[j] % Mod) % Mod; } } for (i = 0; i <= n; ++ i ) { Sum1[i] = Sum2[i], Sum2[i] = 0; // printf ("%lld ", Sum1[i]); } // putchar ('\n'); return Sum1[n]; } signed main () { n = Read (), a = Read (), b = Read (), c = Read (), d = Read (); Int i; for (i = Pow[0] = Fact[0] = 1; i <= n; ++ i ) { Fact[i] = Fact[i - 1] * i % Mod, Pow[i] = Pow[i - 1] * 4 % Mod; } Inv[n] = Getinv (Fact[n]); for (i = n - 1; ~i; -- i ) { Inv[i] = Inv[i + 1] * (i + 1) % Mod; } if (a == b and b == c and c == d ) { for (i = 0; i <= n / 4; ++ i ) { Answer = (Answer + (i & 1 ? -1 : 1) * Pow[n - 4 * i] * Getbinom (n - 3 * i, i) % Mod + Mod) % Mod;; } Write (Answer); return 0; } for (i = 0; i <= n / 4 and i <= a and i <= b and i <= c and i <= d; ++ i ) { // printf ("---------i = %d---------\n", i); Answer = (Answer + (i & 1 ? -1 : 1) * Clac (a - i, b - i, c - i, d - i, n - 4 * i) * Getbinom (n - 3 * i, i) % Mod + Mod) % Mod;; // Write (Answer), putchar ('\n'); } Write (Answer); return 0; }