AT_arc160_f.[ARC160F] Count Sorted Arrays

给定一个整数 $N$ 和 $M$ 个整数对 $(a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)$。每个 $a_i, b_i$ 满足 $1 \leq a_i < b_i \leq N$。

一开始，你拥有 $(1,2,\dots,N)$ 的所有 $N!$ 种排列。
你将进行 $M$ 次操作。第 $i$ 次操作如下：

• 对你拥有的所有 $N!$ 个排列，进行如下处理：
  • 比较排列中第 $a_i$ 个元素和第 $b_i$ 个元素的值，如果前者更大，则交换两者。

对于 $1 \leq i \leq M$，记第 $i$ 次操作结束后你拥有的排列中，已经按升序排列的序列的个数为 $S_i$。
请输出 $S_1, S_2, \dots, S_M$。

不过，输入中给出的并不是 $(a_i, b_i)$，而是整数对 $(x_i, y_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)$。

输入以如下格式从标准输入读入。

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $\cdots$ $x_M$ $y_M$

输出 $M$ 行。第 $i$ 行输出 $S_i$。

数据范围

• $2 \leq N \leq 15$
• $1 \leq M \leq 5 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $0 \leq x_i, y_i \leq N - 1$

样例解释 1

一开始拥有的排列为 $(1, 2)$ 和 $(2, 1)$。$(a_1, b_1) = (1, 2)$。第 $1$ 次操作后拥有的排列为 $(1, 2)$ 共 $2$ 个。因此输出 $2$。

样例解释 2

$(a_i, b_i)$ 依次为 $(1, 2), (2, 3), (1, 3), (1, 2)$。

样例解释 3

$(a_i, b_i)$ 依次为 $(1, 2), (3, 4), (1, 5), (2, 3), (4, 5)$。

由 ChatGPT 4.1 翻译