P10360 [PA 2024] Desant 3

PA 2024 4B

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 4 [Desant 3](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/des/)，感谢 Macaronlin 提供翻译** $n$ 个士兵，从左到右编号为 $1$ 到 $n$。每个士兵有两种状态：准备好和未准备好。现对这些士兵下发 $m$ 条命令，第 $i$ 条命令会使得在 $a_i$ 位置和 $b_i$ 位置的士兵交换位置，但只有 $a_i$ 位置的士兵准备好并且 $b_i$ 位置的士兵没有准备好时才能交换，否则无效。 问对于 $1$ 到 $n$ 中的每个整数 $k$，考虑 $\binom{n}{k}$ 种士兵的初始准备情况，其中有 $k$ 个士兵已准备好，求有多少种准备情况可以在进行 $m$ 条命令后，满足所有准备好的士兵形成一段连续区间。你只需要输出种类数对 $2$ 取模后的值即可。

第一行两个整数 $n$ 和 $m\ (2\le n\le 35,1\le m\le 1\,000)$，分别表示士兵数和命令数。 接下来 $m$ 行，每行两个整数 $a_i$ 和 $b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$，描述一条命令。

输出一行 $n$ 个整数，其中第 $k$ 个整数表示有 $k$ 个士兵准备好的所有初始情况中，可以在进行 $m$ 条命令后使得所有准备好的士兵形成一段连续区间的情况数。输出对 $2$ 取模。

如果一开始只有一名士兵准备好，那么无论如何操作，最终准备好的士兵一定形成一个连续的区间。 考虑这样一种情况：除了队列中的第二名士兵外，其他士兵都已准备好。第一个命令不会影响士兵的位置。第二道命令下达后，由于队列中的第一名士兵已准备好，而第二名士兵尚未准备好，他们将交换位置。第三道命令同样没有影响。由于现在队列中的第一名士兵还没有准备好，而队列中的第四名士兵已经准备好，因此他们不会因为最后一道命令而交换位置。最终只有排在第一位的士兵没有准备好。这是 $k = 3$ 时唯一一种满足条件的初始情况。 未取模前的答案为 $[4,0,1,1]$。