AT_abc199_e [ABC199E] Permutation

题目描述

请输出将 $(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$ 个。

输入格式

输入按以下格式从标准输入读入。

$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

输入 #1

3 1
2 2 1

输出 #1

4

输入输出样例 #2

输入 #2

5 2
3 3 2
4 4 3

输出 #2

90

输入输出样例 #3

输入 #3

18 0

输出 #3

6402373705728000

说明/提示

限制条件

• $2 \le N \le 18$
• $0 \le M \le 100$
• $1 \le X_i < N$
• $1 \le Y_i < N$
• $0 \le Z_i < N$
• 输入中的所有值均为整数。

样例解释 1

满足条件的 $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$ 个，不符合要求。

由 ChatGPT 4.1 翻译