AtCoder Beginner Contest 217

https://atcoder.jp/contests/abc217

F - Make Pair

题意

有 $2n$ 个学生从左到右站成一排，有 $m$ 对学生 $(a,b)$ 关系好。每次可以选择一对相邻且关系好的学生出队，并且他们左右的人被视相邻。求所有学生都出队的方案数，答案对 $998244353$ 取模。

数据范围：$1\leq n\leq 200$。

题解

记 $f_{l,r}$ 表示区间 $[l,r]$ 全部出队的方案数。考虑与 $r$ 一起出队的 $k$，则有转移

$$f_{l,r}=\sum_{k}f_{l,k-1}\times f_{k+1,r-1}\times \binom{\frac{r-l+1}{2}}{\frac{r-k+1}{2}}$$

因为两个区间内部的排列数已经包括在 $f$ 内了，只需要考虑这两个区间彼此交错出队的情况。这就相当于是所有的出队操作中钦定一些位置分配给前一个区间出队。

G - Groups

题意

给定 $n,m$，对于 $k=1,2\cdots,n$：将 $n$ 个人分成 $k$ 组，要求标号模 $m$ 相同的人不在同一组，求方案数。答案对 $998244353$ 取模。

数据范围：$2\leq m\leq n\leq 5000$。

题解

设 $f_{i,j}$ 表示前 $i$ 个数分为 $j$ 组的方案数。

• $i$ 单独一组：$f_{i,j}=f_{i-1,j-1}$
• $i$ 并入其他组，前面与它不相容的数有 $\lfloor\dfrac{i-1}{m}\rfloor$ 个，则 $f_{i,j}=f_{i-1,j}\times\max(0,j-\lfloor\dfrac{i-1}{m}\rfloor)$