F - Count Sorted Arrays Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 を満たします。

はじめ、あなたは (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) とする。

制約

  • 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 回目の操作を終了した時点で持っている順列は (1, 2) が 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) です。

Score : 900 points

Problem Statement

There are an integer N and M pairs of integers: (a_1, b_1), (a_2, b_2), \dots, (a_M, b_M). Each pair (a_i, b_i) satisfies 1 \leq a_i \lt b_i \leq N.

Initally, you have all N! permutations of (1,2,\dots,N).
You will perform M operations. The i-th operation is as follows.

  • Do the following for each of your N! permutations.
    • Compare the a_i-th and b_i-th elements. If the former is greater, swap the two elements.

For each 1 \leq i \leq M, let S_i be the number of permutations of yours that are already sorted in ascending order at the end of the i-th operation.
Print S_1, S_2, \dots, S_M.

Here, the input gives you pairs of integers (x_i, y_i) instead of (a_i, b_i).
The values of (a_i, b_i) can be obtained using x_i, y_i, and S_{i-1} as follows. (Let S_0 = 1 for convenience.)

  • Let c_i = ((x_i + S_{i-1}) \bmod N) + 1.
  • Let d_i = ((y_i + S_{i-1} \times 2) \bmod N) + 1. (Here, it is guaranteed that c_i \neq d_i.)
  • Let a_i = \min(c_i, d_i).
  • Let b_i = \max(c_i, d_i).

Constraints

  • 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

Input

The input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
\vdots
x_M y_M

Output

Print M lines. The i-th line should contain S_i.

Sample Input 1

2 1
1 1

Sample Output 1

2

You start with the permutations (1, 2) and (2, 1).
We have (a_1, b_1) = (1, 2). At the end of the first operation, you have two copies of (1, 2), so you should print 2.

Sample Input 2

3 4
0 1
2 1
1 1
0 1

Sample Output 2

2
4
4
6

(a_i, b_i) in order are (1, 2), (2, 3), (1, 3), (1, 2).

Sample Input 3

5 5
4 4
0 4
1 1
2 4
1 2

Sample Output 3

2
4
4
8
16

(a_i, b_i) in order are (1, 2), (3, 4), (1, 5), (2, 3), (4, 5).