#P15463. 开关序列

    ID: 14678 传统题 1500ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-异或抵消状态编码深度优先搜索暴力枚举

开关序列

题目背景

实验室里有一排 nn 个开关,每个开关只有两种状态:关闭记为 00,开启记为 11。

接下来,系统会按照给定顺序执行 mm 条指令。每条指令会观察两个不同位置 u,vu,v:如果第 uu 个开关当前为 11,且第 vv 个开关当前为 00,系统就交换这两个位置的状态;否则什么也不做。

你需要研究所有可能的初始状态。

题目描述

给定 n,mn,m 以及 mm 条指令。对于每一个 k=1,2,ldots,nk=1,2,\\ldots,n,考虑所有恰好有 kk 个位置为 11 的初始 0101 序列。

依次执行全部 mm 条指令后,如果最终序列中所有 11 所在的位置构成一个连续区间,则称这个初始状态是好的。

请你对每个 kk,求出好的初始状态数量对 22 取模后的结果。

输入格式

第一行包含两个正整数 n,mn,m。

接下来 mm 行,每行包含两个正整数 u,vu,v,表示一条指令。

输出格式

输出 nn 个整数,第 ii 个整数表示 k=ik=i 时的答案,对 22 取模。

样例 0 输入

4 4
4 1
1 2
3 4
1 4

样例 0 输出

0 0 1 1

样例 0 解释

取模前,k=1,2,3,4k=1,2,3,4 的答案分别为:

4,0,1,1.4,0,1,1.

例如初始序列为 10111011 时,执行过程为:

$$1011 \rightarrow 1011 \rightarrow 0111 \rightarrow 0111 \rightarrow 0111.$$

最终所有 11 构成连续区间。

附加样例

  • 样例 1 见下发文件中的 ex_polygon1.in/out,该样例满足子任务 22 的限制。
  • 样例 2 见下发文件中的 ex_polygon2.in/out,该样例满足子任务 44 的限制。
  • 样例 3 见下发文件中的 ex_polygon3.in/out,该样例满足子任务 88 的限制。

数据范围与约定

对于所有测试数据,保证:

1≤n≤35,1≤m≤1000,1 \le n \le 35,\qquad 1 \le m \le 1000,

且每条指令满足:

1≤u,v≤n,u≠v.1 \le u,v \le n,\qquad u\ne v.
子任务 特殊性质 分值
11 n≤7, m≤100n\le 7,\ m\le 100 1010
22 n≤15, m≤200n\le 15,\ m\le 200
33 n≤20, m≤200n\le 20,\ m\le 200
44 n≤22, m≤300n\le 22,\ m\le 300 88
55 n≤24, m≤500n\le 24,\ m\le 500
66 n≤26, m≤600n\le 26,\ m\le 600
77 n≤29, m≤800n\le 29,\ m\le 800
88 n≤30, m≤100n\le 30,\ m\le 100,每条指令的 (u,v)(u,v) 在所有可能的有序二元组中均匀随机选择 2525
99 n≤34, m≤900n\le 34,\ m\le 900 88
1010 无特殊限制 55