E - Permutation
解説
/
実行時間制限: 2 sec / メモリ制限: 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