AT_arc160_f [ARC160F] Count Sorted Arrays

[problemUrl]: https://atcoder.jp/contests/arc160/tasks/arc160_f 整数 $ 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 $ を満たします。 はじめ、あなたは $ (1,2,\dots,N) $ の順列を $ N! $ 種類すべて持っています。 あなたは $ M $ 回の操作を行います。$ i $ 回目の操作は次の通りです。 - 持っている $ N! $ 個の順列すべてに対して次の処理を行う。 - 順列の $ a_i $ 番目の要素と $ b_i $ 番目の要素の値を比較して、前者の方が大きければ両者を swap する。 $ 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 $ $ \vdots $ $ 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\ \lt\ b_i\ \leq\ N $ - $ 0\ \leq\ x_i,\ y_i\ \leq\ N\ -\ 1 $ ### Sample Explanation 1 はじめ、持っている順列は $ (1,\ 2) $ と $ (2,\ 1) $ です。 $ (a_1,\ b_1)\ =\ (1,\ 2) $ です。$ 1 $ 回目の操作を終了した時点で持っている順列は $ (1,\ 2) $ が $ 2 $ 個になります。よって $ 2 $ を出力します。 ### Sample Explanation 2 $ (a_i,\ b_i) $ は順に $ (1,\ 2),\ (2,\ 3),\ (1,\ 3),\ (1,\ 2) $ です。 ### Sample Explanation 3 $ (a_i,\ b_i) $ は順に $ (1,\ 2),\ (3,\ 4),\ (1,\ 5),\ (2,\ 3),\ (4,\ 5) $ です。