分数: 900 点
问题陈述
有一个整数 N 和 M 整数对: (a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)。每对 (a_i, b_i) 满足 1 \leq a_i \lt b_i \leq N.
最初,你拥有所有 N! 的排列 (1,2,\dots,N).
您将执行 M 操作。的 i第操作如下。
- 对您的每个 N! 排列。
- 比较 a_i-th 和 b_i- 第一个元素。如果前者更大,则交换两个元素。
对于每个 1 \leq i \leq M,让 S_i 是您的排列的数量,这些排列已在末尾按升序排序 i第次操作。
打印 S_1, S_2, \dots, S_M.
这里,输入为您提供整数对 (x_i, y_i) 而不是 (a_i, b_i).
的值 (a_i, b_i) 可以使用获得 x_i, y_i,和 S_{i-1} 如下。 (让 S_0 = 1 为方便起见。)
- 让 c_i = ((x_i + S_{i-1}) \bmod N) + 1.
- 让 d_i = ((y_i + S_{i-1} \times 2) \bmod N) + 1。 (这里保证 c_i \neq d_i.)
- 让 a_i = \min(c_i, d_i).
- 让 b_i = \max(c_i, d_i).
约束
- 2 \leq N \leq 15
- 1 \leq M \leq 5 \times 10^5
- 1 \leq a_i \lt b_i \leq N
- 0 \leq x_i, y_i \leq N - 1
输入
输入由标准输入按以下格式给出:
N M x_1 y_1 x_2 y_2 \vdots x_M y_M
输出
打印 M 行。的 i- 第行应包含 S_i.
示例输入 1
2 1 1 1
示例输出 1
2
你从排列开始 (1, 2) 和 (2, 1).
我们有 (a_1, b_1) = (1, 2)。在第一个操作结束时,您有两个副本 (1, 2),所以你应该打印 2.
示例输入 2
3 4 0 1 2 1 1 1 0 1
示例输出 2
2 4 4 6
(a_i, b_i) 按顺序是 (1, 2), (2, 3), (1, 3), (1, 2).
示例输入 3
5 5 4 4 0 4 1 1 2 4 1 2
示例输出 3
2 4 4 8 16
(a_i, b_i) 按顺序是 (1, 2), (3, 4), (1, 5), (2, 3), (4, 5).