相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/06/20170614-statement.pdf
题目大意
给你$m(m \le 10^3)$种，第$i$种有$a_i$张，共$n(n = \sum\limits_{i = 1}^{m}{a_i} \le 5000)$张卡
现在把所有卡片排成一排，定义相邻两个卡片颜色相同为一个魔术对
询问恰好有$k$个魔术对的本质不同的排列方式有多少种，对$998244353$取模
定义本质不同为：至少有一位上的颜色不同
解题报告
一看就需要套一个广义容斥原理
于是问题变为求“至少有$x$个魔术对的方案数”
于是我们可以钦定第$i$种卡片组成了$j$个魔术对
然后用一个$O(n^2)$的$DP$来求出至少有$x$个魔术对的方案数
为了方便去重，我们先假设相同颜色的卡片有编号，最后再依次用阶乘除掉
考试的时候就是这里没有处理好，想的是钦定的时候直接去重，但这样块与块之间的重复就搞不了，于是$GG$了
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5009;
const int MOD = 998244353;
int n, m, K, a[N], pw[N], inv[N], f[N][N], C[N][N];
inline int read() {
char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}
inline int Pow(int w, int t) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}
int main() {
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
m = read(); n = read(); K = read();
for (int i = 1; i <= m; i++) {
a[i] = read();
}
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
pw[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
pw[i] = (LL)pw[i - 1] * i % MOD;
inv[i] = Pow(pw[i], MOD - 2);
}
f[0][0] = 1;
for (int i = 1, pre_sum = 0; i <= m; i++) {
pre_sum += a[i] - 1;
for (int j = 0; j <= pre_sum; j++) {
for (int k = min(a[i] - 1, j); ~k; k--) {
f[i][j] = (f[i][j] + (LL)f[i - 1][j - k] * C[a[i]][k] % MOD * pw[a[i] - 1] % MOD * inv[a[i] - 1 - k]) % MOD;
}
}
}
int ans = 0;
for (int i = K, ff = 1; i < n; i++, ff *= -1) {
f[m][i] = (LL)f[m][i] * pw[n - i] % MOD;
ans = (ans + (LL)ff * C[i][K] * f[m][i]) % MOD;
}
for (int i = 1; i <= m; i++) {
ans = (LL)ans * inv[a[i]] % MOD;
}
printf("%d\n", (ans + MOD) % MOD);
return 0;
}
