← 返回题目列表

AtCoder · arc160_f

F. 计数排序数组

中文机器翻译题面 查看原题

分数: 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).