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 翻译