{"problem":{"name":"[PA 2024] Desant 3","description":{"content":"**题目译自 [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$。每个士兵有两种状态：准备好和未准备好。现","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10360"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [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\n$n$ 个士兵，从左到右编号为 $1$ 到 $n$。每个士兵有两种状态：准备好和未准备好。现对这些士兵下发 $m$ 条命令，第 $i$ 条命令会使得在 $a_i$ 位置和 $b_i$ 位置的士兵交换位置，但只有 $a_i$ 位置的士兵准备好并且 $b_i$ 位置的士兵没有准备好时才能交换，否则无效。\n\n问对于 $1$ 到 $n$ 中的每个整数 $k$，考虑 $\\binom{n}{k}$ 种士兵的初始准备情况，其中有 $k$ 个士兵已准备好，求有多少种准备情况可以在进行 $m$ 条命令后，满足所有准备好的士兵形成一段连续区间。你只需要输出种类数对 $2$ 取模后的值即可。\n\n## Input\n\n第一行两个整数 $n$ 和 $m\\ (2\\le n\\le 35,1\\le m\\le 1\\,000)$，分别表示士兵数和命令数。\n\n接下来 $m$ 行，每行两个整数 $a_i$ 和 $b_i\\ (1\\le a_i,b_i\\le n,a_i\\neq b_i)$，描述一条命令。\n\n## Output\n\n输出一行 $n$ 个整数，其中第 $k$ 个整数表示有 $k$ 个士兵准备好的所有初始情况中，可以在进行 $m$ 条命令后使得所有准备好的士兵形成一段连续区间的情况数。输出对 $2$ 取模。\n\n[samples]\n\n## Background\n\nPA 2024 4B\n\n## Note\n\n如果一开始只有一名士兵准备好，那么无论如何操作，最终准备好的士兵一定形成一个连续的区间。\n\n考虑这样一种情况：除了队列中的第二名士兵外，其他士兵都已准备好。第一个命令不会影响士兵的位置。第二道命令下达后，由于队列中的第一名士兵已准备好，而第二名士兵尚未准备好，他们将交换位置。第三道命令同样没有影响。由于现在队列中的第一名士兵还没有准备好，而队列中的第四名士兵已经准备好，因此他们不会因为最后一道命令而交换位置。最终只有排在第一位的士兵没有准备好。这是 $k = 3$ 时唯一一种满足条件的初始情况。\n\n未取模前的答案为 $[4,0,1,1]$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10360","tags":["2024","PA（波兰）"],"sample_group":[["4 4\n4 1\n1 2\n3 4\n1 4\n","0 0 1 1\n"]],"created_at":"2026-03-03 11:09:25"}}