E - Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

(1, 2, 3, \dots, N) を並び替えてできる数列 a であって、以下の条件を満たすものの数を出力してください。

  • 1 \le i \le M を満たす全ての整数 i について、a_1, a_2, a_3, \dots, a_{X_i} の中に Y_i 以下の数は Z_i 個以下しか存在しない

制約

  • 2 \le N \le 18
  • 0 \le M \le 100
  • 1 \le X_i \lt N
  • 1 \le Y_i \lt N
  • 0 \le Z_i \lt N
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
X_3 Y_3 Z_3
\hspace{23pt} \vdots
X_M Y_M Z_M

出力

答えを出力せよ。

入力例 1

3 1
2 2 1

出力例 1

4

条件を満たす a は以下の 4 つです。

  • (1, 3, 2)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

(1, 2, 3) や (2, 1, 3) は、a_1, a_2 の中に 2 以下の数が 2 つあるため条件を満たしません。

入力例 2

5 2
3 3 2
4 4 3

出力例 2

90

入力例 3

18 0

出力例 3

6402373705728000

Score : 500 points

Problem Statement

Print the number of sequences a that are permutations of (1, 2, 3, \dots, N) and satisfy the following condition:

  • for every integer i such that 1 \le i \le M, at most Z_i numbers among a_1, a_2, a_3, \dots, a_{X_i} are less than or equal to Y_i .

Constraints

  • 2 \le N \le 18
  • 0 \le M \le 100
  • 1 \le X_i \lt N
  • 1 \le Y_i \lt N
  • 0 \le Z_i \lt N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
X_3 Y_3 Z_3
\hspace{23pt} \vdots
X_M Y_M Z_M

Output

Print the answer.

Sample Input 1

3 1
2 2 1

Sample Output 1

4

The four sequences a satisfying the condition are:

  • (1, 3, 2)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

(1, 2, 3) and (2, 1, 3) violate the condition, since each of them has two numbers less than or equal to 2 among a_1, a_2.

Sample Input 2

5 2
3 3 2
4 4 3

Sample Output 2

90

Sample Input 3

18 0

Sample Output 3

6402373705728000